Pixel-value-ordering (PVO) appears as an efficient technique for high-fidelity reversible data hiding. This paper proposes a reversible data hiding scheme based on the pairwise PVO framework with improved difference equations. Both the pixel pair selection and the embedding algorithms are also streamlined. The proposed scheme uses a block classification approach based on a local complexity metric. Uniform blocks are processed using the proposed improved pairwise PVO algorithm. Slightly noisy blocks are embedded using a classic PVO scheme and noisy blocks are kept unchanged. The optimal embedding parameters for a given capacity are determined by linear programming. The proposed pairwise PVO approach outperforms other state-of-the-art schemes.