1. A video coding apparatus comprising: a processor; and a memory storing instructions, which when executed by the processor perform a procedure, the procedure including: (a) determining whether or not a peripheral block of a coding target block, which is an object of coding using an intra prediction coding method, is referenceable when generating a predicted image of the coding target block; (b) generating a pixel value of a reference pixel included in a peripheral block determined at (a) to be non-referenceable, based on the determination result of (a) and a pixel value of a reference pixel included in a peripheral block determined at (a) to be referenceable; (c) for each of a plurality of groups arising when a plurality of prediction modes are classified in the plurality of groups such that prediction modes with similar prediction directions are classified into the same group, classifying each of the plurality of groups into either a full evaluation group in which coding costs are evaluated for all prediction modes or a partial evaluation group in which coding costs are evaluated for a part of the prediction modes, based on peripheral block data that represents peripheral blocks containing each of the reference pixels employed when generating the predicted image using one or more prediction modes belonging to individual groups, and the determination result of (a) or a degree of similarity between reference pixels contained in peripheral blocks represented by the peripheral block data or any combination thereof; (d) determining the prediction mode to use as generating the predicted image of the coding target block by evaluating coding costs of all the prediction modes belonging to each of the groups for a group classified at (c) in the full evaluation group, and evaluating coding costs of a portion of prediction modes out of the prediction modes belonging to each of the groups for a group classified at (c) in the partial evaluation group; and (e) generating a predicted image of the coding target block using the prediction mode determined at (d).