Methods, devices, systems and computer program products facilitate embedding and extraction of transactional watermarks into and from a video content. One method for selecting an area for watermark insertion includes selecting a candidate area within a frame of the video content that is smaller in size that the frame itself, adding a first and a second watermark value to obtain corresponding first and second versions of the area, add noise to each of the first and second versions, and perform watermark extraction operations to obtain corresponding correlation values for the selected area. The above operations are repeated using different areas that are selected at pseudo-random offset values from the previously selected areas until the entire video frame is exhausted. One or more areas with the highest correlation value(s) are selected and designated as areas that are suitable for watermark insertion.