Under the Hood: How we Mask our Images

Polyvore users create over 3 million sets every month, mixing and matching their favorite products to express their style. They clip in images from all over the web, like this teal T-shirt from nordstrom.com

As you can see, the shirt image has a light gray background that creates an eyesore when layered with other items in a set:

How do we strip this background away in order to achieve a cleaner look? More importantly, how can we do it for not just this T-shirt, but for any of the 2.2 million images our users clip in every month?

Magic!

Ok, not quite. But we do use ImageMagick software as well as some nifty tricks to do the transformation. Let’s walk through the basic steps.

First, since the background is usually a neutral color, we use ImageMagick's Modulate to boost the color saturation to highlight the difference between the product and the background. In this shirt, we see the teal turn a bright blue:

Next, we replace the background with white, starting at the pixel that is at the xy position of 2,2. We start there since it's almost certainly part of the background and not the product. ImageMagick has a Draw command that replaces pixels that are the same color as the start pixel with a new color. We use Draw to replace background pixels (those the same color as our start pixel) with white pixels. We also use Draw with a fuzz factor so that it also replaces pixels that are similar in color to the starting pixel to account for subtle gradients and variations in the background.

Negate flips all the colors in the image, which renders our white background black.

Threshold changes lighter-colored pixels to white and darker-colored pixels to black, giving us a black and white mask:

Laying this mask on top of our original image using ImageMagick's Composite with CopyOpacity will keep the parts of the original image that are white in the mask and discard the parts that are black. In essence, the mask acts as a stencil to "cut out" the shirt from the original image:

To demonstrate the background removal effect, here is that same final image laid over a dark gray background:

Neat, right?

This technique works great at smaller image sizes, and this was sufficient when the maximum Polyvore set image was 500x500. But with a general trend towards UIs with larger images and retina displays, we needed to render sets at 1024x1024. At this size, that jagged white outline became much more visible.

We figured there had to be a better way. After some research and a lot of trial and error, here’s what we came up with:

We start with the same teal T-shirt, and we do the same Modulate and Draw steps as before:

Here is where we start to stray from our original masking algorithm. The step after this one works better with grayscale input, so we apply Threshold first:

Then we use Potrace, an open-source utility which can convert bitmaps into vectors (SVG in our case). We use it to "trace" our mask, which produces smooth edges instead of jagged ones. It’s already looking better!

Negate to get a mask with white shirt and black background:

And here's what the masked image looks like on a gray background:

We probably could have stopped here. The white outline around the T-shirt is much smoother than in the original, but wouldn't it be better to not have that outline at all?

Let's go back to the mask we made with Potrace.

Potrace draws such perfect lines that the transition between the black background and white foreground is very sharp. When we use Composite with a mask, ImageMagick interprets the black pixels as areas that should be transparent, white pixels as areas that should be opaque, and gray pixels as areas that should be semi-transparent. If we can replace the sudden black to white transition at the mask's edges with a gradient, we should be able to get the white outline in the final image to fade away.

Using the feathering technique described here, we can smooth the boundary between the black and white by Blurring the edges, then applying this gradient to the Blur'd regions:

It's hard to see the difference in the final mask, so here's a closeup of the right sleeve area before and after the feathering:

Notice that the jagged edges have been replaced with smoother lines and curves and the transition between black and white is more gradual.

And the final payoff, our original masking on the left, our current masking on the right:

We're constantly looking for ways to improve every aspect of our product. Even though this may seem like a subtle feature, it represents the kind of detail and polish that we strive for and the lengths to which we go to make Polyvore great.

Got any of your own image processing tips to share?

Polyvore Style Tips: CSS, Javascript and HTML

Shhhh! Don't tell anyone, but the engineers at Polyvore are ... nerds. Most people have the misconception that Polyvore is full of fashion models and editors, but the truth is that Polyvore's a technology company wrapped in a Gucci dress.

Our core web technology enables people to mix and match products from around the web to create works of art or whimsy.

• Save as you browse or import items from external sites with the Clipper
• Create collages (sets) using the Polyvore editor
• Share creations with the 20 million strong Polyvore community or wherever your friends may be.

Our front ends have always been heavy in HTML, JS, and CSS. And over the years, we've learned a ton in building those features and trying to keep up with all the latest and greatest HTML5 features in modern browsers. I wanted to share some of our favourite tricks.

Unless otherwise noted, these all work on the latest couple Safari, Chrome, and FireFox releases (obviously) but also on IE8 and higher. These are Polyvore's supported browsers and it's a decision based on traffic -- 5% or higher. YMMV if you are committed to supporting older versions.

Overflow: hidden/auto

We thought we understood what this does: it hides node content outside the regular flow or fixed size, right?
We were surprised when we found a secondary behaviour: it also seems to cause a block to determine its width according to available space, without clearing floats or wrapping.

I can't count the number of times we've done this:
CSS:

.leftImg { float: left; padding: 4px; border: 2px solid blue; }
.leftImg + .txt { margin-left: 82px; /* 50px for the img + 2*4px padding + 2*2px border + 20px actual margin -- God I hope no one changes this... */ }

HTML:

Fatback spare ribs tri-tip, corned beef andouille 
bresaola swine meatball biltong short ribs. Corned beef brisket 
tail kielbasa rump cow t-bone biltong ham. Hamburger turkey corned 
beef beef ribs swine drumstick.

Fatback spare ribs tri-tip, corned beef andouille bresaola swine meatball biltong short ribs. Corned beef brisket tail kielbasa rump cow t-bone biltong ham. Hamburger turkey corned beef beef ribs swine drumstick.

But with overflow:hidden ...
CSS:

.leftImg { float: left; margin-right: 20px; }
.filling-block { overflow: hidden; display: block; }

HTML:

Fatback spare ribs tri-tip, corned beef andouille 
bresaola swine meatball biltong short ribs. Corned beef brisket 
tail kielbasa rump cow t-bone biltong ham. Hamburger turkey corned 
beef beef ribs swine drumstick.

Fatback spare ribs tri-tip, corned beef andouille bresaola swine meatball biltong short ribs. Corned beef brisket tail kielbasa rump cow t-bone biltong ham. Hamburger turkey corned beef beef ribs swine drumstick.

As with relying on any secondary behaviour, you have to take the primary behaviour with it:
Caveat: filling-block can't have "overhanging" content (i.e. content outside the regular flow) or else it'll clip / get scrollbars.

A more sane box model

When I say 100%, I mean "including my padding and border".

Booooo

* { box-sizing: border-box; -moz-box-sizing: border-box; }

Yay

localStorage for storing locally

We often want to store things locally without enduring the network costs of cookie storage.
One example for Polyvore is storing signed-out users' current composition, potentially a relatively large (~20k) JSON string.

While localStorage may not have the scalability or flexibility as SQLite or IndexedDB, we like it for its ease-of-use (simple key-value pairs) and widespread support. We also have not seen it perform as poorly as some have experienced. Still to be safe, localStorage access shouldn't be part of an interactive operation (e.g. mouse move) or a tight loop.

One piece missing from the localStorage API is cookie-style expiration:

var LocalStorageCache = (function() {
    var WEEK = 1000 * 60 * 60 * 24 * 7;
    var metaKeyPrefix = 'meta_';
    function getMetaKey(key) {
        return metaKeyPrefix + key;
    }

    var lastCleanup = Number(localStorage.getItem('last_cleanup')) || 0;
    if (lastCleanup + WEEK < new Date().getTime()) {
        // Preventative clean once per week.                                                                            
        window.setTimeout(function() { LocalStorageCache.cleanup(); });
    }

    return {
        WEEK: WEEK,
        set: function(key, value, expires) {
            var jsonValue = '(' + JSON.stringify(value) + ')';
            try {
                LocalStorageCache._set(key, jsonValue, expires);
            } catch(e) {
                // Clean up and try again. This may still fail, but gives us a better chance.                           
                LocalStorageCache.cleanup();
                LocalStorageCache._set(key, jsonValue, expires);
            }
        },
        _set: function(key, jsonValue, expires) {
            localStorage.setItem(key, jsonValue);
            if (expires) {
                localStorage.setItem(getMetaKey(key), '(' + JSON.stringify({
                    'createdon': new Date().getTime(),
                    'expires': new Date().getTime() + expires
                }) + ')');
            } else {
                localStorage.removeItem(getMetaKey(key));
            }
        },
        get: function(key) {
            var metaDataStr = localStorage.getItem(getMetaKey(key));
            if (metaDataStr) {
                var metaData;
                try { metaData = eval(metaDataStr); } catch(e) {}
                if (!metaData) {
                    return this.remove(key);
                }

                // Check the expiration.                                                                                
                var expires = Number(metaData.expires);
                if (expires && expires < new Date().getTime()) {
                    return this.remove(key);
                }
            }

            var dataStr = localStorage.getItem(key);
            if (!dataStr) {
                return this.remove(key);
            }
            var data;
            try { data = eval(dataStr); } catch(e2) {} // parse error?                                                  
            return data ? data : this.remove(key);
        },
        remove: function(key) {
            localStorage.removeItem(key);
            localStorage.removeItem(getMetaKey(key));
            return null;
        },
        cleanup: function() {
            localStorage.setItem('last_cleanup', new Date().getTime());
            var keysToDelete = [];
            for (var i = 0, len = localStorage.length; i < len; i++) {
                var key = localStorage.key(i);
                if (key.indexOf(metaKeyPrefix) < 0) {
                    keysToDelete.push(key);
                }
            }
            // If it has an expiration & it's expired, getting the item will clear that key.                            
            keysToDelete.forEach(this.get, this);
        }
    };
})();

And using the local storage API is easy:

LocalStorageCache.set('a', { foo: 'bar' }, 1000 * 5); // Expires in 5 seconds
LocalStorageCache.get('a'); // returns { foo: 'bar' } (the JS hash, not the JSON)

Caveat: You can only store ~5MB into localStorage

Using JS to edit CSS

We typically change a node's style using node.setAttribute('style', 'width:50px') or similar. But sometimes, it would be nice to change an underlying CSS rule. Some uses we've encountered include:

• Fluid / dynamic interfaces may need to update multiple nodes at once. If you edit CSS rules, you reflow the entire document but you only need to do so once.
• We don't want to change every matching element's style attribute directly; just do it once and let CSS handle it -- now and for all future nodes that may be dynamically added
• We want to dynamically add/change/remove :before/:after pseudo-elements

Here's a demo of it in action.
We do use this technique sparingly though. It can be hard to track down the source of CSS rules when the selectors are often generated dynamically (It's not easy to grep for '.' + myClass + ':before') and as mentioned above:
Caveat: Touching CSS causes a full page reflow and repaint -- don't do this during user interaction or in tight loop!

pointer-events: none

This is a CSS style that suppresses mouse and pointer interaction on an element. With this style, mouse-based CSS selectors like :hover and :active do not activate and you get no JS mouse events.

At Polyvore, we use this to avoid nodes from capturing mouse behavior simply because they have a higher z-index or node stacking. This gives us the freedom to use nodes to help with layout, without interfering with interaction.

CSS:

.controls { pointer-events: none; }
.interactive { pointer-events: auto; }

/* Only hovering over the .interactive parts will make .controls turn grey; other parts have no effect */
.controls:hover { background-color: #ccc; }

HTML:

Demo:

Caveat: not supported in IE9 & below. So it's great for polish, but not for cross-browser correctness.

Summary

At Polyvore, we're always looking for new and interesting ways to let the browser do the heavy lifting. We can't wait to see what the browser vendors will support next!

Worker Queue System

In the good old days, Polyvore started out with a very simple, traditional LAMP architecture. Everything more or less directly accessed a bank of MySQL servers, both to service web requests and also batch housekeeping jobs. But our traffic and data set has kept growing and growing. We started to experience massive spikes in our DB load when nightly batch jobs were kicked off. Jobs that would complete in 3 minutes started to take 5 hours.

Fortunately, our infrastructure team has a ton of experience dealing with scalability issues. Their solution was to use a worker queue system to break up massive jobs into smaller chunks, executed by a bank of workers. This approach allows us to utilize our machines better by spreading load throughout the day and also scale jobs by parallel execution of chunks on different worker machines.

Since we used RabbitMQ before, we considered using it as the building block of our worker queue system as well. However, we quickly found out that RabbitMQ falls short in two important aspects:

• RabbitMQ is essentially a generic message bus. This means we needed to extend its functionality to make it a full fledged worker queue system.
• If a task is added to a RabbitMQ queue, there is no native way of inspecting that task while it is queued. That means we won’t be able to check which worker is handling that task, dedupe tasks and more.

After a bit of research we decided to use Gearman. Gearman is a generic framework to farm out work to other machines or processes. It was a great fit for our needs, especially since we use Perl extensively here in Polyvore, and Gearman has a Perl client and APIs. In addition, we already deployed and use Cassandra in production, and Gearman integrates well with Cassandra as its persistent storage.

Our implementation ended up being a light wrapper for Gearman. Our API is very simple:

A way to push a new task onto a named queue:

$queue->send_task({ channel => 'xzy', payload => $payload });

And a worker for consuming tasks in a given queue:

package Polyvore::Worker::XYZ;
use base qw(Polyvore::Worker);

# process is called with each task on the queue
sub process {
    my ($self, $payload) = @_;

    # do stuff

    # driver will auto-retry a few times
    die $exception if ($error);
}

# instantiate a worker and attach to channel to start consuming tasks.
Polyvore::Worker::XYZ->new({ channel => 'xyz'})->run();

The driver for workers will automatically retry the task a few times (with progressive back-off) if an exception occurs. This is very handy in the world of finicky Facebook, Twitter, etc… APIs. The worker system is integrated with our stats collection system which keeps track of jobs processed, time per task, exceptions and more.

We implemented other useful features as well; we have a worker manager that distributes the worker processes/tasks based on the workers cluster load and queue lengths. It is preferable to have a longer pending task queue than overloading the workers cluster. We also implemented a dependency protocol where a worker task can declare itself as dependent on other tasks in the system. That worker task won’t execute until all of its dependencies are complete.

We use the worker queue system both for scaling our backend processes and also for performing asynchronous front-end tasks. For example, our users post a ton of content to external services. Done synchronously, these post operations can hold up the response anywhere from 5 to 30 seconds (or fail entirely and have to be retried). Using the worker queue system we are able to perform these tasks asynchronously in the background and deliver a very responsive user experience.

Today, we have over 40 worker processes and handle over 18 million tasks per day.

Challenges

Sharding batch jobs

We started out by writing simple jobs that got all their data in one SQL statement. That worked for a while until the number of rows in the DB grew to the point that the select would make our read slaves keel over. We have since been sharding our jobs so that they can operate in smaller chunks, typically by operating over id ranges. Instead of processing all 1M rows, we break up the job into 1000 1K id ranges and treat each range as a task for the worker system.

Sharding to even out load based on data density

Some of the problems we solve using our worker queue system have interesting characteristics. These problems require us to split the data into buckets which are not necessarily equal in size in order to maximize efficiency. For example, we use machine learning to categorize items that we import into our index. We do incremental categorization for new items, but we also re-categorize older items that have been changed recently. Since the distribution of updates is biased toward newer items, we create inverse-log sized data buckets to even out the processing time for each group of items. This gives us larger buckets (~10M items) of old items (with few changes), and smaller buckets (~10K items) of new items (with more changes).

Testing

We have a great development environment which allows us to have multiple checkouts to work in. Each checkout can be previewed against development and production databases. We also have a per checkout test environment which allows us to run our test suite against a particular checkout, with its own isolated mysqld instance, Cassandra instance, etc… We also have per user worker queue in unit test.

Worker Queues vs. Map/Reduce

We use Hadoop for big data analysis. Currently we use it for a specific analysis we do on a subset of the data we have. However, we plan to expand our Hadoop deployment so that we can do more batch analysis on a larger portion of our data and in a lot of other use cases. Obviously Hadoop allows us to analyze our data in ways we couldn’t have done before. Using Hadoop also raises the question of which tasks are best suited for our worker queue system and which tasks will benefit more from map/reduce.

Our worker queue system is great for procedural tasks such as user notifications, user emails, posting on Facebook wall, or extracting meta-data from uploaded images. In addition, we use our worker queue system for scheduling Hadoop jobs. All of those tasks are asynchronous, independent and sometimes require a retry mechanism.

Summary

Worker queues are a great way to scale batch jobs, and increase the utilization of computation resources by spreading load to avoid spikes; thus it helps in designing and implementing a scalable architecture. It also lets you provide a better user experience by performing long blocking tasks asynchronously. As we expand our usage of Hadoop, we will continue to assess which tasks are better suited for our worker queue system and which ones can benefit from Hadoop’s map/reduce design pattern. Using the right tool for the job is an important principle. Designing and implementing simple, scalable tools allows us to uphold that principle.

Also See

• IronMQ Cloud based Message Queue
• AWS Simple Queue Service (SQS)
• RabbitMQ
• Gearman

Web Developer Admits: Objective-C > HTML5

Polyvore released its second iOS app recently. Pure native iOS. Yes, the second. Most people don't remember the first version. We launched a PhoneGap based app earlier in the year but removed it from the app store less than a week later. So why the complete change between v1 and v2?


Before I continue, a disclaimer: I love HTML5. I created the Yahoo! Pipes editor back in early 2007 which surprised many when they realized it wasn't flash but HTML+canvas. I love CSS3 hardware accelerated animation (check out the accordion in the Polyvore mobile HTML web site). Local storage is so useful. HTML5 features just make the user experience faster, better.


So why did we want to create an app when we already had a mobile friendly HTML version for webkit-based browsers (iOS and Android)? Engagement. We really wanted to offer up a more compelling user experience, complete with all the things people expect from apps like push notifications. From a business perspective having an installed presence on the device that could keep bringing users back for new content, and potentially shopping through the app, would be ideal.

An HTML5 based approach

Polyvore's front-end code is all HTML, JS and CSS and, given we are a startup with the usual constraints on engineering, we wanted as much code to be the same as we could across our clients. Using a single client codebase rather than using two should make it both quicker to develop the app as well as add any missing features. Its much faster to iterate and leverages our current developer knowledge base. You can also get your app onto other platforms too (iOS and Android)! Sound familiar? This is one of the lures and promises of HTML5 based apps for web companies. These are all good reasons.


So we opted for wrapping and modifying our JS/CSS with PhoneGap (now Cordova). And off we went. We tried mobile jQuery, Sencha and a few other JS frameworks while we were at it. We spent a lot of time trying to make our PhoneGap app feel native using CSS 3D transitions and various other well known tricks. And indeed, working with Webkit as your operating system gives you a great head start - and from a pure familiarity and comfort perspective, it’s just great. Few cross browser woes either (Android webkit, sigh).


But then you start running into stuff thats really hard to control. For example, Polyvore is a graphics heavy site and putting lots of images into a -webkit-overflow-scrolling: touch; accelerated scrolling experience will cause webkit to crash. Sometimes. Occasionally. Memory related? Probably. De-referencing images as they scroll off helps - but you don't get the scroll events delivered when you really need them when you're running in the smoother scroll. These types of issues just kept cropping up. And we kept building more and more special stuff to make it more and more app like. More plugins for PhoneGap, more Objective-C stubs, more special cases. What you end up doing is attempting to rebuild UIKit on the iPhone and view animations for Android (or using a framework that’s doing the same).


It felt like hammering nails into in a wonky floorboard. We fixed one problem and another would pop up. We probably spent over 80% of our time fixing weird side-effect glitches and making our code work within PhoneGap correctly. But eventually we felt it was much better than our HTML mobile version of our site with transitions and notifications and so we launched it.

Lessons learned and relearned

We shouldn't have. Ultimately our first version didn't feel like an app. It was sluggish in places and unpredictable in others. It didn’t have a set editor. People have high expectations when using an app - it has to be fast, the UI response has to be immediate, it needed to have the most used parts of the desktop experience. If it looks like an app, it needs to behave like one - a differentiated, better experience from the web site. Otherwise, why bother? We took it out of the app store a week later.


Some of these reasons may sound very familiar and the Facebook blog post came out mid-way through our development of the second app. We couldn’t have agreed more when we read it.


Unfortunately we’d needed to re-learn an important lesson. It’s all about great products. Not average “ok” stuff, but truly great. It’s something we focus on here at Polyvore and this time we’d missed the mark. We’d spent so much time and effort re-creating UIKit-like functionality in JS/CSS that worked “just like a native app”, we’d lost sight of our goal. Creating something great.

Going native

The best way of creating that awesome app is not to insulate yourself from the power of the operating system you are running on but to embrace it. So we created the new iOS application that’s in the app store today from scratch. We deliberately chose not to leverage another middleware solution like Appcelerator so that we wouldn't be at the mercy of another code-translation layer between UIKit and our code. We wanted performance and predictability. We wanted control. We wanted to build the best app we could.


An obvious caveat. Building an app this way is clearly going to take you longer, possibly a lot longer. You’re re-writing your entire client side interface in a language and environment you are unfamiliar with, and if, like us, your web-oriented engineering team has no iOS experience to build upon, the learning curve is going to be pretty steep.


Reassuringly there were a lot of abstractions and code we could leverage from our JS. We moved our data model over almost directly into Objective-C and re-used our Ajax APIs for fetching and updating data. And while the entire DOM-based UI and JS eventing system had to be thrown out, KVO and NSNotifications coupled with UIKits built-in widgets translated very well.


Even after a few weeks of learning Objective-C and fighting Xcode we knew it was the right choice to deliver the app we wish we'd created the first time. Things that took forever getting working well in HTML5 just work. View transitions, UI Thread prioritization, background threads, view re-use and memory management are all built in. Not added on, but core to the framework.


Quick, fast, snappy. Objective-C is certainly no panacea - it has its own issues and weirdness. It wasn’t a quick and simple “port” and without being able to leverage any other Objective-C knowledge in our organization we did a lot of things wrong before getting them right.

Do you really need an app?

Is HTML5 an abstraction layer too far above where you really should be working, giving you limited interfaces and control of the things you should care about like memory handling, threads, and (ultimately) performance? For simple apps it's tempting to say don't worry about it, it’s the quick thing to do and mobile CSS/JS frameworks will get it done for you. But if your app is simple why is it an app at all? Why bother with something in the middle when Safari is installed on the phone already and your app will always be a subset of your mobile traffic? 


So before you start coding your app ask yourself if you really need one. An HTML5 version of your site in the web browser can behave however you want it to without confounding users’ expectations. If you want to create the best user experience possible for the iPhone don’t try to fake the iOS look and feel, you’ll spend too much time on the things you get for free from a native iOS app and not enough delivering the meat of your experience. So bite the bullet, learn Objective-C, and produce that awesome app that will bring joy to your users.

Polyvore Infographic

It's been a great year for Polyvore!

To celebrate the end of 2012, we've put together an infographic showcasing our growth.

Our amazing community of users has grown and grown. We now have over 20 million unique visitors per month. Our community creates over 2.4 million sets per month, which get viewed 1 billion times per month. 43% of those views happen on social networks like Facebook and Pinterest. (Interestingly, sets shared to Pinterest get seen 18x as often as those shared to Facebook.)

Polyvore drives 7.5 billion views of products per month, which attracts lots of people who shop -- and spend! The average order size from Polyvore visitors is a whopping $220. On Black Friday, our average basket was 50% higher than the average for apparel. Fun fact: the biggest order ever was for $67,315!

A big thank you to the Polyvore community and to our wonderful team for a great year! Looking forward to 2013 :-)

Happiness at Startups

Go here to read our co-founder and CEO Jess Lee's thoughts on why many startup founders are unhappy (but she's not, because she loves Polyvore :-).

Her basic premise is that happiness is the first derivative of success, so your really feel all the ups & downs that are a natural part of any startup.  Even if you're on a general upwards trajectory, you still feel the downward momentum of the little bumps along the way.





The secret to staying happy is to have a great culture and great people.  It's the glue that keeps things together through the downs.  You should also remember where you came from and talk to other founders to get some perspective.



You can read the full post here.

Why Software Engineers are (Vastly) Undervalued

Our co-founder and CTO Pasha Sadri wrote a great post on his personal blog about why software engineers are often undervalued at other company.  (Not ours though!)

During my tenure at Yahoo (circa 2001 – 2007) I learned how to do a lot things, but just as crucially, how not to do certain things. Chief amongst the latter was how not to treat engineers. Yahoo, despite many well-intentioned efforts and notable exceptions, did not empower engineers. Even though we engineers created tons of value, it was the non-engineers who were often the gatekeepers. 

Eventually many of the best people noticed, got fed up and left. After I left in 2007 to co-found Polyvore, one of my main goals in life became building an environment that highly values engineers and treats them as first class citizens. I continue to strongly believe that all sorts of good things follow from that. I have since been thinking about why engineers are systematically undervalued compared to more traditional roles given the tremendous value they create. I have come up with three sociological reasons:

You can read the rest of the post here.