WaitableButton
We held our first every Hack Day (Happy Pi Day!) today at ADstruc. Every month, we’re going to be devoting one day to build a small-but-useful piece of software and open source it. That’s right, open source it! Giving back to the community is a core part of our company culture, and we’re super-excited to express this value through our product development process. This time around we built WaitableButton, a jQuery plugin that can be used to add a waiting state while binding a jQuery $.ajax() object to your buttons. Check out some examples, or download it now!
ORM + RDB != ODM + MongoDB
MongoDB has been the target of a considerable amount of hate from the community of late. Here’s the backstory — in 2008 began a “mass exodus” of sorts towards (immature) NoSQL technologies. Bright-eyed architects began adopting databases like MongoDB without developing a complete understanding of their features and limitations. Over time, they realized the err of their ways. The full implications of the loss of the relational and ACID properties of the RDBMSs that they had abandoned only became clear as their applications grew. Their thoughts of 1000 machine mongo clusters were replaced by the realities of rewriting GROUP BY in code for the twelfth time; these early adopters began ranting and raving against poor lil’ Mongo.
That said, this is not another MongoDB-is-a-PITA-post. Sure, we’ve run into our own share of issues with Mongo. But to us, the most interesting ones have arisen from our use of an ODM (Object-Document Mapping) system as an abstraction of Mongo. We decided to use Mongo because it seemed to be a good fit for early versions of our application – we used its geospatial features heavily, and had a handful of primary domain objects that were more or less disjoint. However, as the application evolved and our data started to look more and more relational, we decided to adopt Doctrine’s ODM (heavily inspired by their ORM which in turn is modeled after Hibernate) to act as a bridge between the document paradigm and the traditional relational paradigm. In a lot of cases, this abstraction works well but in others, it breaks down; Doctrine’s ODM is a leaky abstraction. As Joel Spolsky puts it in his Law of Leaky Abstractions:
“All non-trivial abstractions, to some degree, are leaky.”
An ODM is an incredibly difficult abstraction to implement. It attempts to create an ORM-like mapping, which is already conceptually and technically tricky due to the impedance mismatch between the OO and relational paradigms, for a datastore that is very different from a traditional RDB. In some cases, these differences can be worked around in code, resulting in additional complexity and inefficiency. In other cases, the differences remain, and are rendered invisible to the ODM user; the biggest danger of this sort of abstraction lies in the fact that it creates an illusion of similarity. Users of the ODM, like us, fall prey to concluding incorrectly that since it looks like, swims like and quacks like an ORM, it probably is one. Under the hood lies a very different beast. Here are some of the ways in which we were bitten by way of such thinking:
1. Workaround for lack of nested positional operator caused unexpected results
Mongo’s positional operator does not support the ability to update arrays nested within arrays (an issue present since March 2010). However, our domain model consists of many one-to-many-to-many style relationships that are implemented as array embeddings by the ODM at the DB level. For instance, we have a ‘proposal’ object which has a one-to-many relationship with a ‘property’ which in turn has a one-to-many relationship with a ‘message’ which in turn has a one-to-many with ‘attachment’; a proposal document contains an array of property documents and so on… However, since the positional operator can only perform updates up to one-level deep (in this case, to properties only), updates to further levels of nested arrays must be performed by a workaround in code. Because of a bug in the ODM to work around this limitation, we found that when trying to add a message with attachments to a property, the attachments would always get added on to the first message in the array. Going forward, we’re working around this workaround by avoiding more than one level of nesting — normalizing our data across multiple documents in such cases. This comes at the cost of performance, and the cost of increasing the probability of data inconsistency issues (due to lack of multi-document atomic updates i.e., transactions). This inconsistency in how Mongo treats top level documents vs. embedded documents is not only an issue with the Doctrine ODM, but also with the popular Mongoid ODM as well.
2. Unexpected query implementation caused race conditions
In a feature that kicked off multiple asynchronous updates to a certain object, we discovered a bug that seemed to be causing the data corresponding to a certain property on the object to disappear. After a few hours of digging deep into the internals of the ODM, we discovered that the bug was caused by an unexpected implementation of what we assumed was an atomic write. While aware that Mongo doesn’t implement transactional support, we assumed that single-document ODM level updates were mapped to single-document updates at the DB level and hence, were atomic (would be a pretty safe assumption in the case of most ORMs). However, we noticed that while updating the value of a property on an object that is an ArrayCollection type (a Doctrine collection type which wraps native PHP arrays), the ODM executed two queries on the corresponding document – one to unset the property (rendering it empty), and a second to set it to the specified value. This, of course, led to a race condition when multiple processes tried to write/read changes to/from this object. Often, processes that tried to update the object after an update to the ArrayCollection property was initiated by an earlier process, read the object in a state in which the property was unset. These processes wrote the object with the property in the unset state, making it seem like data was disappearing.
3. Emulation of joins causes performance issues
Most ORM’s support the retrieval of an object graph from the underlying database with a single query but since MongoDB does not support joins, the retrieval of an object and its associations involves many roundtrips to the database resulting in a process that is obviously less efficient (admittedly, we are yet to quantify the extent of the performance hit). The number of queries that the ODM must perform in order to retrieve an object graph is more or less opaque to a developer who is not conscientiousness of this limitation of the database — another downfall of this abstraction.
Even though abstractions enable developers to write cleaner code faster, they also increase the risk of their making incorrect behavioral assumptions. This is especially true when abstractions that are generally well understood are recreated for disparate underlying systems. However, we agree with Jeff Atwood in that the most useful (non-trivial) abstractions (also the most leaky) are here to stay. It is our job as programmers to understand the deficiencies of such abstractions and not reject them, for in return they promise us much simplicity.
Using Selenium to automate testing Google Maps in your application
With the latest release of our new buyer tools, we’ve placed a heavy emphasis on mapping. In order to make sure that we’re providing a stable, well-tested platform for all of our users, we rely on Selenium to automatically run through our most common workflows before each new release. If you don’t know what Selenium is, it’s a standalone server that allows you to programmatically control a web browser (plugins are available for Firefox, Chrome, and Internet Explorer). You can easily determine if elements exist on the page, click links, execute JavaScript, take screenshots, and many other tasks. By stringing these various tests and tasks together, you can generate a programmatic path through your website/application to ensure both that it behaves as expected between browsers and that changes to your code do not break existing functionality. To learn more, visit the Selenium homepage.
When we were looking around for a good resource on getting started with Selenium and Google Maps, we found that many of the articles out there were about v2 of the Google Maps API and the few StackOverflow posts only covered the absolute first steps of getting up and running. We’ve grouped together some of the tips and tricks we’ve learned along the way of building out our test suite.
With the proliferation of browser technologies such as Canvas, Google kept optimizing Maps to handle more markers and more layers, faster than ever before. The downside to this (from the Selenium testing perspective) is that many of these optimizations break the normal pattern one uses when writing a Selenium test. Luckily, Google has given us a way to disable these optimizations when creating a marker, by setting optimized to false in the google.maps.MarkerOptionsobject.
Rather than inserting the marker into one of its existing Canvas tiles, this causes Google Maps to render it as individual DOM (Document Object Model) element. Be forewarned, you should only do this for development/Selenium testing purposes, as the performance penalty is quite noticeable. At ADstruc we do this by including the environment inside a globally accessible ADstruc object on the page and then only modifying the google.maps.MarkerOptions object when we’re in our testing environment.
Side note – while Google Maps disables right clicking on elements within the map container, it’s still possible to use Web Inspector to inspect elements within the map by using the magnifying glass and then clicking on the element.
Now that you and Selenium can actually find the markers within the DOM, how do you go about picking out a specific one? Unfortunately, Google Maps doesn’t tie a specific ID onto a marker or provide a way of programmatically accessing the underlying DOM element. This makes sense because, except for cases where the optimizations are specifically turned off, there are no DOM elements to directly reference from the marker object. There are a few tricks we can combine into a serviceable workaround. The first is that all markers belong to the class gmnoprint. However, all of the map controls (zoom, layers, copyright bar, etc.) also belong to this class. Most of these you can turn off when initializing the map, but a few (the copyright bar and report a map error) are always there. If you’re trying to get a count of the markers on the map, it’s a good idea to take a baseline reading of the number of elements that belong to the gmnoprintclass before adding the markers in.
More likely, you are going to want to interact with a specific marker – check if it’s on the map, mouseover it, click it, etc. To do this requires a bit more digging into the structure of a marker element and the commandeering of its title attribute. There are two distinct structures, one for markers with events and another for those without. The markers without events are very simple and the title is attached to the containing div element:
The ones with events have a few more elements to support making the marker image clickable. Here, the events and the title are attached onto the area element:
In terms of being able to set arbitrary data onto the DOM element of a marker, the title element is, currently, our only option. At ADstruc, we don’t use the title attribute in our actual application, so it was easy to take it over for identification purposes. If your application does make use of the title attribute, you’re going to have to implement a switch so that you can safely use it during testing purposes. For our application, we have three types of markers – Points Of Interest (one from the Google Places API and another saved into our system) and Units. All three of these have IDs that are unique, so it was easy for us to simply set the title to <type>-<id> during testing. We’re using Facebook’s WebDriver library, but these examples should be applicable no matter which language you’re using.
Note – you could replace this with an XPath selector as well, however, we’ve always found the regular selectors much easier to debug and XPath under Internet Explorer can run into some speed issues depending on the complexity of your selectors.
Now that you’ve got your marker selected, you can pretty much treat it as you would any other Selenium element. Remember that if you want to trigger events, you’re going to need to select the area element (which is also the one where the title element is attached). We haven’t had the need to interact with polylines just yet, but they may prove to be a more difficult challenge, since there doesn’t seem to be an optimized attribute in the google.maps.PolylineOptions.
If you’re looking to purchase outdoor advertising and haven’t had a chance to check out the most efficient way to do so, click here to schedule a demo with one of our account managers.
– Andrew
Billboard Detection
At 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!
