PVO-based schemes are the widely-used reversible data hiding (RDH) techniques. Benefiting from the good prediction performance, the stego-image can have a high quality. However, the complexity metric of PVO is still not good enough. The two main limitations are: the block-based context pixels are not highly correlated with the predicted pixel, and the fluctuation-based complexity calculation methods cannot comprehensively represent the real prediction result. Unlike the existing complexity metrics, we consider this problem from a novel viewpoint of neighborhood pixel prediction (NPP), i.e., using the prediction pixel to predict the unmodified neighborhood pixels of a predicted pixel. The neighborhood pixels are more reliable than the context pixels and the generated neighborhood prediction-errors (NPEs) are utilized to represent the real prediction-error (RPE). Two new features are extracted from NPEs as Dual-complexities to determine the embedding order. Experimental results indicate the quality of the stego-image can be improved significantly by using our proposed Dual-complexities in the related PVO-based schemes, and it can be directly extended to other schemes in PVO framework as well. © 2024 Elsevier B.V.