I have been going through this paper, and wish to implement the same algorithm in java. I have also managed to write equivalent code for the same, but I have not completely understood the mathematics of the algorithm. In the section 2 'Algorithm', can anybody explain to me how equation 1, 2, 3 and 4 yield a large sparse system of linear equations?
The algorithm is given as input an intensity volume Y (x, y , t ) and outputs two color volumes U (x, y , t ) and V (x, y , t ). T o simplify notation we will use boldface letters (e.g. r, s) to denote (x, y , t ) triplets. Thus, Y (r) is the intensity of a particular pixel. As mentioned in the introduction, we wish to impose the constraint that two neighboring pixels r, s should have similar colors if their intensities are similar . Thus, we wish to minimize the difference between the color U (r) at pixel r and the weighted average of the colors at neighboring pixels:
eq.1) $J(U) = \sum_{r}{\Big(U(r) - \sum_{s \in N(r)}{w_{rs}U(s)} \Big)^{2}}$
where wrs is a weighting function that sums to one, large when Y (r) is similar to Y (s), and small when the two intensities are different. Similar weighting functions are used extensively in image segmentation algorithms.
eq.2) $w_{rs} \propto e^{-(Y(r) - Y(s))^{2}/2 \sigma_{r}^{2}}$
A second weighting function is based on the normalized correlation between the two intensities:where µr and σr are the mean and variance of the intensities in a window around r.
eq.3) $w_{rs} \propto 1 + \frac{1}{\sigma_{r}^{2}} \big(Y(r) - \mu_{r} \big) \big(Y(s) - \mu_{r} \big)$
The notation r ∈ N(s) denotes the fact that r and s are neighboring pixels. In a single frame, we define two pixels as neighbors if their image locations are nearby . Between two successive frames, we define two pixels as neighbors if their image locations, after accounting for motion, are nearby . More formally , let vx (x, y), vy (x, y) denote the optical flow calculated at time t . Then the pixel (x0, y0, t ) is a neighbor of pixel (x1, y1, t + 1).
eq.4) $|| (x_{0} + v_{x}(x_{0}), y_{0} + v_{y}(y_{0})) - (x_{1}, y_{1}) || < T$
Now given a set of locations ri where the colors are specified by the user u(ri ) = ui, v(ri ) = vi we minimize J( U ), J( V ) subject to these constraints. Since the cost functions are quadratic and the constraints are linear , this optimization problem yields a large, sparse system of linear equations, which may be solved using a number of standard methods.