The BSS technique, which we will talk about with more depth later on, is a world-wide known technique used to separate a number of signal sources from a number of mixtures.
Abstract
The BSS technique, which we will talk about with more depth later on, is a world-wide known technique used to separate a number of signal sources from a number (can be different from the number of sources) of mixtures. The mixtures must be linear combinations of the sources, they must also be sparse enough, and the sources must all be independent one of the other in order to get satisfying results.
The two main types of this Algorithms is the Clustering technique, and the ICA(Independent Component Analysis). The latter technique(ICA) is basically an optimization Algorithm which runs on a probabilistic framework, for example a Maximum a Posteriori approach assuming that the noise is white Gaussian . The first technique(Clustering) runs on the assumption(at least in the 2sources-2mixtures case) that at each point (in space/time), only one of the sources has an intensity large enough to notice. This assumption, of course can’t be proved, but is based on probabilistic calculations.
In both techniques the results will be much more satisfying if we use sparse signals, leading us to try to use sources that are sparse. Be that as it is, our world sometimes doesn’t supply us with our wishes, and thus leaving us with sources which are anything but sparse. In order to overcome this obstacle, we use techniques to achieve sparsity.
The first is to simply just analyze these signals on a different base. We will pick a base, whom which the projection of our signal(on the base) will use a small amount of base vectors. This will cause our signal to be sparse in this base. The commonly used bases are the wavelet packet group due to their very promising traits in causing signals to become sparse “looking”.
The second technique is to work with the derivative of the signals using different types of derivative kernels (Laplacian, Sobel, specials).
We will use variations of these techniques, and many other interesting approaches in order to achieve optimal results in separating fog from images, i.e “”Vision Through Mist””.
Tools
Basic BSS algorithm (ICA)
Now, once we have understood the great power of the BSS technique, one would ask when exactly and how he can use this algorithm. The basic form of the BSS technique is 
Where:
X- the mixes matrix(row-wise)
A- the mixture matrix(represents how the mixture was built)
S- the source matrix(row-wise)
In the two dimensional & 2 source – 2 mixture form they hold the following structure:
Where:
– the row stack form of the 
Picture.
– the row stack form of the 
Picture.
– the row stack form of the 
Picture.
– the row stack form of the 
Picture.
One would want to use this technique when he can fullfill the following:
- He has in control 2(mixtures(X1,X2) which are constructed by 2 Independent sources S1,S2
- The two mixtures are independent one of the other
- The two mixtures are independent linear combinations of two sources S1,S2
* One could also use this algorithm with more sources than mixtures if the mixtures are sparse enough.
To run the algorithm and achieve the sources:
1. Build the rowstack form of the pictures(X1,X2) and insert them into the X matrix(while maintaining the structure from above).
2. Use a BSS algorithm to achieve the 
matrix.
3. Achieve S using 
4. Extract 
, 
from S(Si is the i-th row of S)
5. Construct S1, S2 from , .
What to do if the mixtures aren’t so sparse?
If the mixtures that you control aren’t sparse enough(you ran the algorithm and didn’t achieve good results) then you can use sparsity techniques such as moving to a different base representation(Wavelet packets), or work with the derivative of the mixtures. This will be explained in more depth in the next section.
Achieving Sparsity
As we stated above, to receive good results from the basic BSS algorithm, we want to use sparse representations of our Mixtures. We used to basic techniques to do this:
Using wavelets for sparsity
The first technique is based on using a wavelet dictionary. We will represent our images in a different base such that the coefficients of the base vectors(the wavelet dictionary) will be sparse. We will be left with only the matrix of coefficients. We can describe this action of moving from one base to another by matrix multiplication(base transformation can be represented by matrix multiplication).
We can see this in the following example( 1D case, in the 2D case we can use the row stack representation to return to the 1D case):
Lets assume we are given the following vector :
and we wish to represent it on another base :
From basic Linear Algebra we know that the signal can be represented in the other base as(assuming (19) ):
when 
.
we can equally write this in matrix form as:
Such that the new bases vectors are placed as the rows of the transforming matrix.
Now we can reanalyze our BSS problem:
Our original problem:
If we represent both the X & S Images in a different base represented by the 
function, such that the base vectors are placed as the columns of the rows(we are multiplying from the right).
If we use the following transformation:
Where 
, 
denote the images in the new base(
)
Then the original problem transforms into the following:
And since is built as base vectors for columns, it is invertible, and we receive:
Which leaves us with a different BSS problem but with the same mixing matrix A:
If we solve this problem for A then we can use it on the original problem to receive S. This is used to our advantage because the A achieved resulting from this BSS problem will be much more precise due to the sparsity of the mixture signals.
We can obtain, once again, the original source signals after we have found A:
The hard part in the base transforms is to pick a base which will leave us with a sparse representations. Wavelet packets are very strong in this property , therefore are used a lot in this category.
Signals Derivative Technique
A second technique which works well on smooth pictures, is achieving sparsity using the signals derivative. The derivative of a smooth signal would naturally be much more sparse than the original. We can represent this derivation in the matrix form as an action Matrix ‘D’.
Our original problem:
transforms into the following:
If we denote XD=X’ , SD=S’ then we receive:
This is in fact a different BSS problem, but it has the same mixing matrix(A) of the original. If we solve this problem for A then we can use it on the original problem to receive S. This is used to our advantage because the A achieved resulting from this BSS problem will be much more precise due to the sparsity of the signals in X.
We can obtain, once again, the original source signals after we have found A:
Simple BSS demonstration
To demonstrate the power of the BSS technique, we took two pictures, Peppy(the dog) and Lena:
The original pictures
and constructed two linear mixtures:
We can insert these two pictures into the ICA BSS algorithm which will weave not so satisfying results. In order to achieve the results we want, we first run derivative filters on the pictures and then our results are magnificent:
We can see that to the eye it seems like we completely separated the sources from the linear mixtures.
Conclusions
The results of Vision Through Mist using various BSS techniques were a failure. This, of course, does not come to us as a surprise if we would just remember all of the assumptions which aren’t necessarily true:
1. The fog acts as additive noise
2. The fog structure doesn’t change between the two different pictures
3. The kernel in different spectrums is a constant times the basic kernel, meaning
4. The mixtures are constructed by a linear combination between the fog image and the picture
From our lack of success we can conclude that not all of these assumptions are correct, and that the BSS technique on our type of model is not a strong one(compared to other techniques vision through mist techniques)
There is also a small chance(but we doubt it) that the assumptions were right and the bad results were the cause of a technical error, such as:
1. The light wasn’t exactly a “”white light””
2. The camera wasn’t focused well at all(the hyper- spectral) camera that we used is meant for filming objects at hundred meter distances, while we tried to use it to film a close object.
3. etc.
What we did conclude that was rather surprising was the great effect of using derivatives for sparsity. We demonstrated in chapter 1 the results of seperating 2 mixtures of “”Lena”” and “”Pepe”” pictures using the derivatives for sparsity. Also, throughout the running of the algorithm in our experiment, we received much better results using the derivative sources technique for sparsity instead of the wavelet packet technique.
Acknowledgment
We would like to thank our project supervisor: Eli Appleboim
The Labs engineer: Johanan Erez
And all of the experts in this area of work which helped us out with out research:
Alex & Michael Bronstein, Ran Kaftory, Dr. Yoav Y Schechner, Dr. Michael Zibulevsky
We are also grateful to the lab’s stuff and to the Ollendorff Minerva Center Fund who supported this project.