Video steganography is used to conserve the confidential information in various security applications. To give advance protection to the secrete message, pixels locations are optimized using nature inspired algorithm. The input video is separated into a sequence of still image frames then key frames are extracted. The proposed Required Pixel Density (RPD) value calculation and feature extraction are carried out on the extracted frames to perform the frame classification. The frame classification is done using proposed Fractional Water-Earth Worm optimization algorithm based Deep Convolutional Neural Network (FrWEWO-Deep CNN) in order to classify the frames as high, low and medium quality. Thus pixel location prediction is carried out using trained Deep CNN then secret image is hide within high quality frame with Wavelet Transform (WT) and Inverse WT (IWT). Peak Signal to Noise Ratio (PSNR) and Correlation Coefficient (CC) are performance evaluation parameters. For efficient video steganography better imperceptibility and robustness are required. Imperceptibility is a scale of PSNR value showing similarity between original and stego video frames. The robustness of video steganography is measured by CC between embedded and extracted secret images. The proposed algorithm gives enhanced performance is compared with previous state of art such as WEWO-Deep RNN. The PSNR value is progressed from 41.8492 to 46.5728 dB and CC value improved from 0.9660 to 0.9847.