I would avoid using sparse matrices unless you really need matrices for computing, and store indices and values in numeric arrays that can be preallocated, even by block (e.g. by 100MB increments). I would also avoid using cell arrays. Instead, I would use a frame index, e.g.
X = [ 10, 5, 22, 1, 8, 9, ... ]
Y = [ 5, 8, 20, 30, 7, 6, ... ]
I = [ .... ]
F = [ 1, 1, 1, 2, 3, 3, ... ]
where F is the frame ID. This way I would deal only with the simplest and most efficient data structure available in MATLAB.
If you want to optimize memory usage, you can also prealloc these arrays using the smallest (size-wise) suitable class (e.g. uint8 or 16 for X and Y), but I suspect that it will introduce a time overhead. It will also prevent you from computing directly with the stored values (except for basic operations, you'll have to type cast relevant blocks back to double first).
Note 1: if you perform comparisons with sparse matrices (as mentioned in comments below), keep in mind that in MATLAB sparse matrices are only working with doubles. Also, you could build a "smarter" way of coding elements positions (typically the one used internally for storing sparse matrices [ ref ]), but encoding would take time. Yet, you have this possibility to exchange time efficiency for memory efficiency.
