# Projection Experiment
In the open source implementation of [dehazing with color lines by Tomlk](https://github.com/Tomlk/Dehazing-with-Color-Lines), the distance metric that is used during ransac is different from the metric mentioned in [Fattal paper](https://www.cse.huji.ac.il/~raananf/projects/dehaze_cl/). We will explore the validty of this alternative form. 


## Fattal's Formula
Fattal paper's defines the similarity metric (distance) between two  direction as follows (paraphrased): 

$D = I(x_2) - I(x_1)$ - Direction vector of the color line.   
$V = I(x_1)$ - Point on the color line.  
$\Omega$ - The set of pixels in an image patch

Each line is associted with pixels $x \in \Omega$ that support it, i.e., pixels in which $I(x)$ is sufficiently close to the line. **This is measured by projecting $I(x) - V$ onto the plane perpendicular to $D$ and computing the norm of the projected vector.** In our implementation we associate a pixel with the line if the norm falls below $2 \times 10^{-2}$.

Let $\hat{D} = I(x) - V$.    
Fattal's formula can be written as: 

$$Distance = ||\hat{D}-\frac{\hat{D}\cdot D}{||D||^{2}}D||$$  
The projection onto the plane is calculated as $\hat{D}$ minus its component that is not orthogonal to $D$.
$$ $$


## Tomlk's Formula
The formula used in Tomlk's implementation can be written as: 
 
$$||\frac{D\times\hat{D}}{||D||}||$$  
  
No further explanation is provided, so we will have to figure it out ourselves. Intuitively, the fraction makes sense as the norm of the cross product will increase when the angle between $D$ and $\hat{D}$ is larger (the norm of the cross product equals the [area of the parallelogram](https://en.wikipedia.org/wiki/Cross_product)). The denominator $||D||$ may possibly be a scalar that removes any effect the magnitude of $D$ may have (thereby treating it as a unit vector). Before proving the equality of these formulas, we can test them to rule out some obvious counter examples.


```python
import numpy as np 
np.random.seed(2)

def explicit_project(vec1, vec2): 
    """ Returns length of projection of vec2 onto a plane perpendicular to vec1. 
        Fattal's Formula.
    """
    dot = np.dot(vec2, vec1)
    squared_norm = np.linalg.norm(vec1)**2
    proj_onto_vec1 = (dot / squared_norm) * vec1
    proj_onto_plane = vec2 - proj_onto_vec1
    result = np.linalg.norm(proj_onto_plane)
    result = abs(result)
    return result

def implicit_project(vec1, vec2):
    """ Returns the length of the cross project scaled to the lenght of vec1.
        Tomlk's Formula. 
    """
    cross_product = np.cross(vec1, vec2)
    norm = np.linalg.norm(vec1)
    scaled_cross_product = cross_product / norm 
    result = np.linalg.norm(scaled_cross_product)
    result = abs(result)
    return result    

differences = list()
for i in range(1000):
    v1 = np.random.rand(3)
    v2 = np.random.rand(3)
    # Randomly scale random vectors
    v1 = v1 * np.random.randint(1000)
    v2 = v2 * np.random.randint(1000)
    explicit = explicit_project(v1, v2)
    implicit = implicit_project(v1, v2)
    difference = explicit - implicit
    differences.append(difference)
    
differences = np.array(differences)
print('The largest difference is equal to : {}'.format(differences.max()))
# The largest difference is equal to : 2.2737367544323206e-13
```

    The largest difference is equal to : 2.2737367544323206e-13


Such a small difference over so many samples is a good sign. Now let's prove the equality.

## Equality proof

$$||\hat{D}-\frac{\hat{D}\cdot D}{||D||^{2}}D|| = ||\frac{D\times\hat{D}}{||D||}||$$  
$$||\hat{D}-proj_{D}\hat{D}|| = ||\frac{D\times\hat{D}}{||D||}|| $$

Given the propetry $||\frac{\vec{1}}{x}|| = \frac{||\vec{1}||}{x}$

$$ = \frac{||D \times \hat{D}||}{||D||} $$ 

Given the property $||a\times b|| = ||a||\hspace{0.1cm}||b||sin(\theta)$

$$ = \frac{||D||\hspace{0.1cm}||\hat{D}||sin(\theta)}{||D||}$$  

$$= ||\hat{D}||sin(\theta)$$  

Now if we draw $D$, $\hat{D}$, $P = proj_{D}\hat{D}$, and $W = \hat{D}-P$$ we have:    
<div style="text-align:center">

</div>


We see the vectors draw compose a right triangle :     
With a hypotenuse of length $||\hat{D}||$   
Two legs of length $||P|| = ||proj_{D}\hat{D}||$   
and  $||W|| = ||\hat{D}-proj_{D}\hat{D}||$  

Let us consider the trigonometric definition of sin.    
 
 
<div style="text-align:center">

</div>

This means that 
\begin{align}
sin(\theta) &= \frac{||W||}{||\hat{D}||} \newline \newline
&= \frac{||\hat{D}-proj_{D}\hat{D}||}{||\hat{D}||}
\end{align}

Now we all necessary steps to complete the proof: 

\begin{align}
||\hat{D}-proj_{D}\hat{D}|| &= ||\frac{D\times\hat{D}}{||D||}||\newline  \newline
 &= \frac{||D \times \hat{D}||}{||D||} \newline  \newline
 &= \frac{||D||\hspace{0.1cm}||\hat{D}||sin(\theta)}{||D||} \newline  \newline
 &= ||\hat{D}||sin(\theta) \newline \newline
 &= ||\hat{D}|| \frac{||\hat{D}-proj_{D}\hat{D}||}{||\hat{D}||} \newline \newline
 &= ||\hat{D}-proj_{D}\hat{D}|| \newline \newline
 ||\hat{D}-proj_{D}\hat{D}|| &= ||\hat{D}-proj_{D}\hat{D}||
\end{align}
   
$$ True $$


3f9b6cdf4230c111e2d015f6d44bac71a707076a
ipynb
Jupyter Notebook
Experiment_notebooks/2_projection_experiment.ipynb
LittleLittleZE/dehazing_using_color_lines
86609bee3f1cbe9bb17af915d9a18b83a744044c
MIT
2021-01-12T08:44:03.000Z
2022-03-28T04:56:12.000Z
Experiment_notebooks/2_projection_experiment.ipynb
LittleLittleZE/dehazing_using_color_lines
86609bee3f1cbe9bb17af915d9a18b83a744044c
MIT
Experiment_notebooks/2_projection_experiment.ipynb
LittleLittleZE/dehazing_using_color_lines
86609bee3f1cbe9bb17af915d9a18b83a744044c
MIT
2020-05-03T08:45:31.000Z
2022-01-01T00:48:23.000Z
Qwen/Qwen-72B
1. YES
2. YES