At the cost of high complexity, the existing spatial error concealment algorithms may slightly improve the recovery quality by iterative approximation, and some algorithms are optimized only for certain loss patterns. To achieve a trade-off among performance indices, this paper proposes a non-iterative shrinkage multi-directional (NSM) prediction algorithm aiming at handling various types of loss patterns. For the error concealment of the current missing block, the proposed NSM algorithm firstly adopts an isotropic gradient detector to learn the local feature information of the current extrapolation region. Based on a basic concealment unit with 16-pixel neighbor and eight prediction directions, the multi-directional predictor recovers each pixel of the missing block one by one in a shrinkage filling order, and adjusts the weighting coefficients of the predictor according to the availability of adjacent pixels. During the shrinkage filling of a block, different pixel groups are recovered group by group according to their neighbor-level availabilities, and different missing pixels in a pixel group are predicted one by one according to a priori filling rule. Thus, non-iterative reconstruction with low complexity can be realized. Compared with other spatial error concealment algorithms, experimental results show that the proposed NSM algorithm achieved better overall reconstruction performance under various loss patterns, and realized a competitive performance trade-off among versatility, computational complexity, and recovery quality.