Towards a more effective storage of transitions

A Markov model of $N$ prototypes needs to store a matrix of transition probabilities of size $N^2$. For instance, if we have found $1000$ prototypes in a few minutes of video, a matrix of $1000000$ values will be required. One can easily imagine the figures for a couple of hours of video.

Furthermore, in a standard Markov model and with our kind of data, a lot of transition probabilities will be either null or insignificant. Indeed, in a video sequence of an object, the trajectories of the object is often continuous and does not jump randomly from one position to another. So when the object is in a position corresponding to one prototype, no more than 2 or 3 prototypes can model its next position in the sequence, maybe more in particular cases. The next position cannot be modeled by the whole set of prototypes since physical restrictions on the objects do not allow this. In the transition matrix, all of the impossible configurations are modeled by a probability of zero.

In some other situations, the transition probability is very low. Such situations can include atypical behaviours that happened only once during the training stage. In this case, we may want to discard this transition since it does not reflect representative situation. A low probability transition can also come from the hardware used to capture the video sequence. A slow computer may drop some frames when the user is running a resource consuming process during a small time. This will result on sudden jump of the object within the sequence, and so an atypical behaviour. The same effect can be achieved if a recorded video sequence has not been correctly encoded in digital format.

It would be better not to store these values since it is really likely that we do not need them. The variable length Markov model brings a solution to this problem because it discards small probabilities and also transition that do not add any useful information to the model. The transition probabilities storage needs to be rearrange for efficiency.

In the VLMM model, the transition probabilities are encoded in a tree. Figure 5.1 shows such a tree. Figure 5.1(a) represents the standard storage in VLMM as described in [51]. Figure 5.1(b) represent the way we have stored the probabilities. We can easily map the two ways of storing probabilities. Our storage is more efficient in retrieving probabilities in the way we are interested in, but the gain is negligible compared to the other sources of computation.

Figure 5.1: Example of storage of transitions in a VLMM model. The two way of storing the probabilities are equivalents. From 5.1(a) we can deduce for instance the probabilities $P \left({\cal{P}}_{3}=B\vert{\cal{P}}_{2}=B,{\cal{P}}_{1}=A \right)=0.2$ , or $P \left({\cal{P}}_{2}=C\vert{\cal{P}}_{1}=A \right)=0.3$. From 5.1(b) we can deduce the probabilities $P \left({\cal{P}}_{3}=B,{\cal{P}}_{2}=B,{\cal{P}}_{1}=A \right)=0.072$ , or $P \left({\cal{P}}_{2}=C,{\cal{P}}_{1}=A \right)=0.18$.

Each branch of the tree represents a transition probability. In this case, the set of prototypes is $\{A,B,C\}$. A prototype, a position in the history and a vector is associated with each node. The size of the vector is the same as the size of the set of prototypes. Each element in the vector corresponds to a immediate child. If the value in the vector is null, the corresponding child is not drawn on the tree. On figure 5.1(b), it stores the probability of having this child and all the prototypes seen so far on their respective positions in the history.

For instance, the node $B_2$ corresponds to the prototype $B$ at the position $2$ in the history. The second element in the vector associated with the node $B_2$ correspond to the probability of $B$ (the second prototype) being at the position 3 (one step further in the history) given that the history ends with the sequence $B,A$. Using mathematical notations, the second element in the vector associated with the node $B_2$ is the probability $P \left({\cal{P}}_{3}=B,{\cal{P}}_{2}=B,{\cal{P}}_{1}=A \right)$ , that is the probability of having the sequence $B,B,A$. The end of this sequence corresponds to the nodes $B_2$ and $A_1$ that need to be crossed to reach $B_3$.

On figure 5.1(a) The vector stores the probability of having a child at its corresponding position in the history given that all the nodes seen so far are placed on their respective positions in th history.

For instance, the second element in the vector associated with the node $B_2$ corresponds to the probability of $B$ being the third in the history given that $B$ is the second and $A$ is the first, that is : $P \left({\cal{P}}_{3}=B\vert{\cal{P}}_{2}=B,{\cal{P}}_{1}=A \right)$ .

This tree representation of the storage is also called a prediction suffix tree. It is proved in [52] that a prediction suffix tree is equivalent to a finite state automata. So it is also equivalent to a transition matrix as used by Markov models.