Billboard Detection
By Madhav KrishnaAt ADstruc we’re constantly importing and updating inventory for our 800+ Out-of-Home media (includes billboards, subway ads, telephone kiosks etc. – check out OOH-101) partners. The inventory data that we receive is usually comprised of excel sheets listing the ad-spaces/units, accompanied by photo sheets containing unit photographs. Over time, we’ve developed tools to help us assimilate this data automatically. The part that has proved most challenging to automate is the generation of crops from the photo sheets to produce images that conform to the dimensions that we use on the site. It’s difficult because the position of the units in the photographs is arbitrary. So, for instance, in cases in which the photograph is taken on approach on a highway, the unit might be placed to the side (left or right) of the photo. Hence it’s impossible to make assumptions about unit position. Here are some examples:
Further, our platform supports a Creative Upload feature which allows an advertiser to preview their creative on a unit before choosing to buy it. In order for the creative image to be superimposed on the unit, its four corners need to be pre-identified (if it is a parallelogram – most OOH units are).
Recently, we developed a billboard detection algorithm (using Python and the open-source image processing library, OpenCV), to identify the unit in a photograph automatically, crop around it and return its four corners.
Thankfully, the units are usually outlined, or are flood-filled in the provided photos – this provides us with a great signal to start. However, since the images are highly compressed, artifacts such as ringing make it non-trivial to detect unit boundaries with great accuracy. We began by thresholding the image – allowing a range of colors resembling the outline/flood color to pass through. We hand-picked a narrow initial range and a wide final range. The algorithm successively backs-off to the wider range until a parallelogram is found. Here’s the binary image obtained from thresholding the first image show above:
Given the thresholded binary image, our first attempt at billboard detection involved the use of the Harris Corner Detection algorithm. However, given the edgy nature of the boundary in binary image, the algorithm ended up identifying a large set of “corners” (points with low self-similarity), not including the actual corners of the shape in some cases. This method was too sensitive to the presence of pixels from extraneous objects. Here the output obtained from applying the Harris Corner Detection algorithm to the binary image shown above (corners are marked by green circles):
Our second attempt involved the use of simple geometry to extract a parallelogram from the binary image. We calculated the center of the unit outline by averaging pixel co-ordinates (assuming that only outline pixels made it through the thresholding step). The corners were then determined by computing the point farthest from the center, the point farthest from this point, the point farthest from the line joining the two points, and lastly, the point farthest from the line joining the two points but on opposite side of the line that the third point lay on. However, this method broke down (quite badly!) in cases when pixels from extraneous objects made it to the thresholded image.
Our third and most successful approach involved the use of many techniques. We began by applying the Contour Detection algorithm given by Suzuki et al. to determine the extreme outer contours in the binary image, using simple chain contour approximation. Then, we applied the Douglas-Pecker Polygon Approximation algorithm to the determined contours. From the computed polygons, we retained only approximate parallelograms (quadrilaterals with parallel sides, or almost so) with a certain minimum area. If more than one parallelogram was found, the one with the largest area was retained. This method proved most successful, and we observed a recall of 80% and a precision of 91%. Given the four corners of the “billboard” it was trivial to find its bounding box, and crop around it. The corners were stored for the purpose of the aforementioned Creative Upload feature.
The outputs from our most successful approach, when applied to the first two images in this post, are shown below (detected billboard corners are marked by green circles):
Next, we’re going to try to apply a supervised machine learning algorithm to this problem while seeding it with the labelled data obtained from the unsupervised technique described here. Stay tuned!
1 Notes/ Hide
- eyeheartnewyork liked this
- adstructech posted this