PCA, Compressive Measurements, and Video

So, I've been having a little bit of fun with visualizations today. The outcomes were pretty nice and potentially artistic, so I thought I'd share them with everyone. Let me explain what you're looking at here:

I've been investigating (for a while now) the recovery of video from compressive measurements. One of these techniques we presented at DCC earlier this year and is also part of another article submission. One of the core procedures of this technique involves harvesting all of the possible blocks within a search window in a reference frame surrounding a target block location. All of these blocks are then ranked according to their proximity to the target block using the \(\ell_2\) norm. Those of you familiar with traditional video coding will be familiar with this technique of block matching from ME/MC. The basic idea here is that these proximities are similar under random projection, so we can compare projected reference blocks against block compressive measurements and come up with some decent frame predictions. That is for some reference block dataset \( \mathcal{H} \), \( | \mathcal{H} | = K\) for all references \( h_{1, \dots, K} \in \mathcal{H} \), that the set of all pairwise distances, \( \{ || h_i - h_j ||_2 ;  i, j \in 1, \dots , K\}\), has its salient structure preserved under random projection, that is, \( \{ || \Phi (h_i - h_j) ||_2 ;  i, j \in 1, \dots , K\}\). This observation is nothing more than just restating portions of works on the JL Lemma. The application to block matching happens when we can say with a high liklihood that $$ arg \underset{i \in 1, \dots, K}{min} || x - h_i ||_2 \approx arg\underset{i \in 1, \dots, K}{min} || \Phi ( x - h_i ) ||_2 .$$

This ends up working out pretty well in practice.

For these visualizations, I originally wanted to see if there was any kind of clustering going on within the set of reference blocks, \( \mathcal{H}\). In order to visualize this high dimensional data, I just did the most direct thing and took the first three principal components of the reference dataset and then scatter plotted the coefficients of each reference in the dataset. In otherwords, if the matrix \( P \) contains the first three PC's of \( \mathcal{H} \), then each point in these images, \( p_i \) is calculated as $$ p_i = P^T h_i .$$ I used the same procedure for the set of projected reference blocks, as well, except here the principal components, \( Q \), are calculated from the set \( \{ \Phi h_i ; i \in 1, \dots K \} \). Then, each point \( q_i \) is calculated as $$ q_i = Q^T \Phi h_i .$$

In order to fit some extra information in there, I color coded the data points. The points \( p_i \) are mapped on the white->red->black scale. The points on the white->blue scale represent the points \( q_i \). Increasing color intensity represents increasing accuracy, or proximity, to the true/target block for each, \( || x - h_i ||_2 \). This same set of proximities was also used for displaying the colors of \( q_i \) as well, to give some consistency across both. The size of each point also increases as its proximity to the true/target block increases. Also, for reference, I just used projections with coefficients drawn from a normal distribution \(\Phi \sim \mathcal{N}(0,1)\).

What is really cool about these visualizations is that they show the similarity between point clouds and their random projections. I also included a little animation that shows one such cloud unfolding as the number of measurements increases. 

The other interesting aspect that these visualizations show is that most of these reference blocks seem to lie on some kind of manifold. This makes some sense, because we can think of these blocks as articulated, that is, they can be described by a set of parameters, namely the pixel location of each block. This is why manifold theory might be productive for super-resolution or sub-pixel ME/MC. I also find the intricate structures that show up in these visiualizations are especially cool. I would not have expected to see some of the shapes that are shown, here. Maybe I need to spend some more time with manifolds!