Optimal time segmentation for overlap-add systems with variable amount of window overlap

In this letter, we propose a new best basis search algorithm for computing the optimal time segmentation of a signal, given a predefined cost measure. The new algorithm solves a problem that arises when the individual signal segments are windowed and overlap-add is applied between adjacent signal segments. When windows having a variable tail shape are employed, the minimization of a cost measure is faced with dependencies between segmental costs due to varying window overlap. A dynamic programming-based algorithm is presented that takes into account these dependencies. It computes both the optimal split positions and the optimal amount of window overlap at these split positions in polynomial time. The proposed algorithm gives an upper bound to the achievable performance of existing algorithms. Experimental results for a modified discrete cosine transform-based processing system are presented, both for entropy and rate-distortion cost measures. These results show a performance gain over existing schemes at the cost of an increased computational complexity.