Proximal methods have gained much interest for solving large-scale possibly non smooth optimization problems. When dealing with complicated convex functions, the expression of the proximity operator is however often non explicit and it thus needs to be determined numerically. We show in this work how block-coordinate algorithms can be designed to perform this task. We deduce also distributed optimization strategies allowing us to implement our solutions on multicore architectures. Applications of these methods to video restoration of old TV sequences illustrate the good performance of the proposed algorithms.