Video watermarking can effectively protect the copyright of video contents, but how to improve efficiency of watermarking algorithms is an urgent problem to be solved. In this paper, QRCode is embedded in the scene change frames of videos based on the advantage of QRCode’s strong fault tolerance. Combined with the characteristic of high decoding reliability of QRCode, a strategy to terminate the extraction process in advance is proposed to improve the extraction efficiency of the watermark algorithm. Experimental results show that the proposed algorithm has higher extraction efficiency than the algorithm that directly uses character string as watermark.