Multi-threaded implementations of deblock filtering improve encoding and/or decoding efficiency. For example, a video encoder or decoder partitions a video picture into multiple segments. The encoder/decoder selects between multiple different patterns for splitting operations of deblock filtering into multiple passes. The encoder/decoder organizes the deblock filtering as multiple tasks, where a given task includes the operations of one of the passes for one of the segments. The encoder/decoder then performs the tasks with multiple threads. The performance of the tasks is constrained by task dependencies which, in general, are based at least in part on which lines of the picture are in the respective segments and which deblock filtering operations are in the respective passes. The task dependencies can include a cross-pass, cross-segment dependency between a given pass of a given segment and an adjacent pass of an adjacent segment.