At Flipboard, we are working hard to build the world’s best personal magazine—a magazine made just for you, filled with the stories you care about most. Magazine layout design plays a key role in telling those stories. Good layout design frames a story and impacts how you are informed by the content. For example, in the hallways of Sports Illustrated, editors hang up every page of the print edition to be reviewed and manually tweaked before publication. When you read Flipboard, articles and photographs are laid out in a series of pages you can flip through, just like in a print magazine. Each magazine page layout feels hand-crafted and beautiful—as if editors and designers created it just for you. How do we automate the whole process of layout design and editing? By slotting your content into custom designed page layouts—like fitting puzzle pieces together. We start with a set of page layouts created by human designers. Then, our layout engine figures out how to best fit your content into these layouts—considering things like page density, pacing, rhythm, image crop and scale. In many ways, that is the key to Flipboard’s signature look and feel: at its heart are the work of real designers.

In the Beginning

In 2010, we built Flipboard Pages, a layout engine that turns web page articles into magazine pages for the iPad. Flipboard Pages paginates content from world-class publications including Vanity Fair and National Geographic. Pages can produce beautiful layouts, replicating the brand identity and custom typography of each publication. Pages used CSS3, SVG and vanilla JavaScript to make rendering as high fidelity and performant as possible on constrained mobile devices. (such as the original iPad running iOS 3.2) The download footprint for a publication’s layouts averaged around 90K for layouts, styling, fonts and nameplate images–lighter than the equivalent web page or a single photograph from an article. A designer first creates a set of about 20 page layouts, divided up into portrait (768×1004) and landscape (1024×748) orientations. From this set, Pages selects the layout that best fits the desired content, inserts the content into the layout, and produces a final page. With this example-based approach, we rely on designers to make layouts clear, distinct and beautiful. While Pages could create great layouts, they only worked at a specifically designed size. Web and Windows 8¹ presented a new challenge: Users can resize browser windows to any size, at any time. To support arbitrary sizes, we needed something better.

Introducing Duplo

Duplo is a new layout engine that starts with the ideas in Pages but uses a modular block and grid system to quickly fit content into thousands of page layouts in all sizes. See for yourself: open this magazine on the web, flip a few pages, then resize your browser window randomly for a bit. Flipboard’s page layouts will instantly adapt to fit the available window size. That’s Duplo in action. Duplo starts in a similar way as Pages: A designer creates a set of layouts. From this set, Pages selects the layout that best fits the desired content. However, while Pages looks at about 20 candidate layouts, Duplo looks at anywhere between 2000 to 6000 candidates, searching for the best layout to fit the content.

Implementation

Like Pages, Duplo is a JavaScript-based engine that runs in your web browser. JavaScript offers rapid development, portability and first-class functions; CSS3 gives a strong base for typography and formatting. This approach keeps our footprint light and scales well to Retina devices. Duplo runs in four main stages: creating layouts, selecting layouts, refining layouts and displaying layouts.

Creating Layouts

Designing 2000+ layouts by hand quickly becomes untenable, so Duplo’s layout generator assembles smaller pieces into larger layouts according to a designer’s guidelines. A designer’s guidelines for page balance and harmony can be nuanced, so we simply represent these guidelines as example layouts, building up a tree of possible full layout options, much like a tree of valid chess moves. Duplo also considers hand-made full-page layouts alongside assembled layouts when searching for the best match.

Selecting Layouts and Applying Content

Once Duplo has generated a set of layout permutations, Duplo has to figure out which of the 2000+ layouts is the best match to use for the given content. First, Duplo compares the contents’ structure against the layout’s content slots to see how closely it matches. Next, Duplo computes the best pairings of content with slots, by optimizing a fitness function built on dozens of individually-weighted heuristics. Some of these heuristics are: Page flow. We apply Perlin noise to give an organic sense of variety to the types and number of items on a page. The component noise functions approximate how an editor might pace elements through magazine pages. [caption id="attachment_17673" align="alignnone" width="1373"] Visualizing page flow scoring weight changes.[/caption] Amount of text to fill the given frame. We estimate the percentage of the frame that will contain the text, giving higher weights to text that fills 80% or more of the frame. Content coherence across window resizes. Items that were previously present on a page are given a weighted bonus when they appear together in a candidate layout. More weight is given if items maintain a similar ordering. Image feature detection, aspect ratio, scale, crop. We calculate the amount of scaling and cropping needed for an image to fit the frame, giving higher weights to images that best fit the frame with minimal crop and upsampled scaling that doesn’t exceed 120%. We also perform server-side detection of important image features, such as faces and foreground subjects, using OpenCV. [caption id="attachment_17672" align="alignnone" width="1300"] Image scale, crop and feature detection matching.[/caption] Brute force searching through all the possible candidates can be very slow. Duplo prunes the candidate search space with a branch and bound algorithm discarding options that don’t yield an optimal fit. It is a lot like efficiently searching for the best next move in a chess game. All these heuristics serve to approximate what human designers or editors do when laying out a magazine.

Refining Layouts

Once an optimal layout is chosen, Duplo refines the layout. Frames are aligned to a baseline grid. Image frames are sized to best fit a target image. Frames styled with full-bleed attributes are extended to the page boundaries. [caption id="attachment_17682" align="alignnone" width="1214"] Before refinement. Note that text and headlines are not aligned to the baseline grid.[/caption]

Displaying Layouts

When Duplo reaches the rendering stage, most of the puzzle has been solved. We now have a refined, well-considered layout that can be rendered a number of ways. But for this discussion, the layout is rendered lazily as an HTML DOM. Images are loaded, scaled and cropped, dynamic data is fetched. Text is now precisely flowed into layout frames, either overflowing in the case of article text, or resized in the case of headline text. Duplo uses a type scale to size headline text down according to a designer’s specifications—lighter weights at large sizes and heavier weights at smaller sizes, all chosen by a designer to work well together. A headline set in descending steps of a type scale. Larger size text is set in lighter weights, smaller size text in heavier weights. Duplo will adjust until the headline fits within the bounding region, and if possible, optimize for a 1.61 width to height ratio.

Conclusion

In so many ways, the story of Flipboard is emblematic of the modern age: the best results often come from a partnership between humans and technology. The predominant narrative of this age of networked hardware and software is the displacement of humans by computers and robots, but again and again, when we look at the best possible results in areas like curation, recommendations, and personalization, the optimal strategy pairs humans with software. Similar approaches are used in visual effects. Image-based rendering uses reference photographs and simple models to photorealistically render new scenes. Photographs capture all the dirt and detail in the real world that CG artists cannot fully recreate, allowing a visual effects team to cross the uncanny valley.² The same is true for dynamic content layout: we achieve far better results by fitting content to a large set of designer-created layouts rather than approximating layouts with a more pure algorithmic approach such as linear constraints. [caption id="attachment_17675" align="alignnone" width="1865"] Sample article page layouts at various sizes from I Want To Go To There by Paul Katz.[/caption] Ultimately, what we’ve done with Pages and Duplo is take the elements of magazine layout design—a powerful tool in framing a story and its impact on the reader—and created a way to automate the process, while still capturing the essence and art of a human designer’s craft. As we continue this journey, it’s exciting to imagine how humans and computers will work closer together to break new frontiers in art and science. While we’re happy with what we’ve made so far, we’re never satisfied–there is still so much more to do. If you are interested in working on these kinds of problems, we’re hiring. 🙂

This post first appeared on 2014-03-23 in TechCrunch.

1. 1. Flipboard for Windows 8 is a hybrid app that is 90% web based. ↩

1. In 2000, The Matrix, one of the first films to use image based rendering, won an Academy Award for Visual Effects, beating Star Wars: Episode I, a film packed with cutting edge but traditionally created CG visual effects. ↩

Thanks to Eugene, Eric, Todd, Andrew, Boris, Ethan, Johan, Josh, Irene, Geert, Anh and Michael for reading drafts of this. by Charles Ying