A method of encoding a video into a bitstream using decoder-side intra mode derivation, wherein the video comprises a plurality of frames, each frame comprising blocks of samples, comprising: determining costs of using respective candidate intra prediction modes to predict samples in a template region adjacent to a current block of a video frame, wherein determining the costs comprises: in an initial stage, determining costs of using respective intra prediction modes from an initial set of candidate modes, wherein index numbers respectively associated with the candidate modes in the initial set are separated by an initial interval, and in at least one subsequent stage, determining costs of using respective intra prediction modes from a subsequent set of candidate modes, the subsequent set of candidate modes being selected based on the candidate mode in the previous stage having the lowest cost, wherein index numbers respectively associated with the candidate modes in the subsequent set are separated by a subsequent interval smaller than the interval used in the previous stage; deriving an intra prediction mode having the lowest cost among the candidate intra prediction modes, wherein the derived mode is included in a list of most probable modes, and wherein an index is encoded into the bitstream identifying the derived mode from the list of most probable modes; and predicting the samples in the current block using the derived intra prediction mode, wherein the subsequent set of candidate modes is centered on the candidate mode in the previous stage having the lowest cost. determining costs of using respective candidate intra prediction modes to predict samples in a template region adjacent to a current block of a video frame, wherein determining the costs comprises: in an initial stage, determining costs of using respective intra prediction modes from an initial set of candidate modes, wherein index numbers respectively associated with the candidate modes in the initial set are separated by an initial interval, and in at least one subsequent stage, determining costs of using respective intra prediction modes from a subsequent set of candidate modes, the subsequent set of candidate modes being selected based on the candidate mode in the previous stage having the lowest cost, wherein index numbers respectively associated with the candidate modes in the subsequent set are separated by a subsequent interval smaller than the interval used in the previous stage; in an initial stage, determining costs of using respective intra prediction modes from an initial set of candidate modes, wherein index numbers respectively associated with the candidate modes in the initial set are separated by an initial interval, and in at least one subsequent stage, determining costs of using respective intra prediction modes from a subsequent set of candidate modes, the subsequent set of candidate modes being selected based on the candidate mode in the previous stage having the lowest cost, wherein index numbers respectively associated with the candidate modes in the subsequent set are separated by a subsequent interval smaller than the interval used in the previous stage; deriving an intra prediction mode having the lowest cost among the candidate intra prediction modes, wherein the derived mode is included in a list of most probable modes, and wherein an index is encoded into the bitstream identifying the derived mode from the list of most probable modes; and predicting the samples in the current block using the derived intra prediction mode, wherein the subsequent set of candidate modes is centered on the candidate mode in the previous stage having the lowest cost.