New Challenges in Computer Science Research

Posted by Jeff Walz, Head of University Relations

Yesterday afternoon at the 2012 Computer Science Faculty Summit, there was a round of lightning talks addressing some of the research problems faced by Google across several domains. The talks pointed out some of the biggest challenges emerging from increasing digital interaction, which is this year’s Faculty Summit theme.

Research Scientist Vivek Kwatra kicked things off with a talk about video stabilization on YouTube. The popularity of mobile devices with cameras has led to an explosion in the amount of video people capture, which can often be shaky. Vivek and his team have found algorithmic approaches to make casual videos look more professional by simulating professional camera moves. Their stabilization technology vastly improves the quality of amateur footage.

Next, Ed Chi (Research Scientist) talked about social media focusing on the experimental circle model that characterizes Google+. Ed is particularly interested in how social interaction on the web can be designed to mimic live communication. Circles on Google+ allow a user to manage their audience and share content in a targeted fashion, which reflects face-to-face interaction. Ed discussed how, from an HCI perspective, the challenge going forward is the need to consider the trinity of social media: context, audience, content.

John Wilkes, Principal Software Engineer, talked about cluster management at Google and the challenges of building a new cluster manager-- that is, an operating system for a fleet of machines. Everything at Google is big and a consequence of operating at such tremendous scale is that machines are bound to fail. John’s team is working to make things easier for internal users enabling our ability to respond to more system requests. There are several hard problems in this domain, such as issues with configuration, making it as easy as possible to run a binary, increasing failure tolerance, and helping internal users understand their own needs as well as the behavior and performance of their system in our complicated distributed environment.

Research Scientist and coffee connoisseur Alon Halevy took to the podium to confirm that he did indeed author an empirical book on coffee, and also talked with attendees about structured data on the web. Structured data is comprised of hundreds of millions of (relatively small) tables of data, and Alon’s work is focused on enabling data enthusiasts to discover and visualize those data sets. Great possibilities open up when people start combining data sets in meaningful ways, which inspired the creation of Fusion Tables. An example is a map made in the aftermath of the 2011 earthquake and tsunami in Japan, that shows natural disaster data alongside the locations of the world’s nuclear plants. Moving forward, Alon’s team will continue to think about interesting things that can be done with data, and the techniques needed to distinguish good data from bad data.

To wrap up the session, Praveen Paritosh did a brief, but deep dive into the Knowledge Graph, an intelligent model that understands real-world entities and their relationships to one another-- things, not strings-- which launched earlier this year.

The Google Faculty Summit continued today with more talks, and breakout sessions centered on our theme of digital interaction. Check back for additional blog posts in the coming days.

Video Stabilization on YouTube

Posted by Matthias Grundmann, Vivek Kwatra, and Irfan Essa, Research at Google

One thing we have been working on within Research at Google is developing methods for making casual videos look more professional, thereby providing users with a better viewing experience. Professional videos have several characteristics that differentiate them from casually shot videos. For example, in order to tell a story, cinematographers carefully control lighting and exposure and use specialized equipment to plan camera movement.

We have developed a technique that mimics professional camera moves and applies them to videos recorded by hand-held devices. Cinematographers use specialized equipment such as tripods and dollies to plan their camera paths and hold them steady. In contrast, think of a video you shot using a mobile phone camera. How steady was your hand and were you able to anticipate an interesting moment and smoothly pan the camera to capture that moment? To bridge these differences, we propose an algorithm that automatically determines the best camera path and recasts the video as if it were filmed using stabilization equipment. Specifically, we divide the original, shaky camera path into a set of segments, each approximated by either a constant, linear or parabolic motion of the camera. Our optimization finds the best of all possible partitions using a computationally efficient and stable algorithm. For details, check out our earlier blog post or read our paper, Auto-Directed Video Stabilization with Robust L1 Optimal Camera Paths, published in IEEE CVPR 2011.

The next time you upload your videos to YouTube, try stabilizing them by going to the YouTube editor or directly from the video manager by clicking on Edit->Enhancements. For even more convenience, YouTube will automatically detect if your video needs stabilization and offer to do it for you. Many videos on YouTube have already been enhanced using this technology.

More recently, we have been working on a related problem common in videos shot from mobile phones. The camera sensors in these phones contain what is known as an electronic rolling shutter. When taking a picture with a rolling shutter camera, the image is not captured instantaneously. Instead, the camera captures the image one row of pixels at a time, with a small delay when going from one row to the next. Consequently, if the camera moves during capture, it will cause image distortions ranging from shear in the case of low-frequency motions (for instance an image captured from a driving car) to wobbly distortions in the case of high-frequency perturbations (think of a person walking while recording video). These distortions are especially noticeable in videos where the camera shake is independent across frames. For example, take a look at the video below.

Original video with rolling shutter distortions

In our recent paper titled Calibration-Free Rolling Shutter Removal, which was awarded the best paper at IEEE ICCP 2012, we demonstrate a solution to correct these rolling shutter distortions in videos. A significant feature of our approach is that it does not require any knowledge of the camera used to shoot the video. The time delay in capturing two consecutive rows that we mention above is in fact different for every camera and affects the extent of distortions. Having knowledge of this delay parameter can be useful, but difficult to obtain or estimate via calibration. Imagine a video that is already uploaded to YouTube -- it will be challenging to obtain this parameter! Instead, we show that just the visual data in the video has enough information to appropriately describe and compensate for the distortions caused by the camera motion, even in the presence of a rolling shutter. For more information, see the narrated video description of our paper.

This technique is already integrated with the YouTube stabilizer. Starting today, if you stabilize a video from a mobile phone or other rolling shutter cameras, we will also automatically compensate for rolling shutter distortions. To see our technique in action, check out the video below, obtained after applying rolling shutter compensation and stabilization to the one above.

After stabilization and rolling shutter removal

Gamification for Improved Search Ranking for YouTube Topics

Posted by Charles DuHadway and Sanketh Shetty, Google Research

In earlier posts we discussed automatic ways to find the most talented emerging singers and the funniest videos using the YouTube Slam experiment. We created five “house” slams -- music, dance, comedy, bizarre, and cute -- which produce a weekly leaderboard not just of videos but also of YouTubers who are great at predicting what the masses will like. For example, last week’s cute slam winning video claims to be the cutest kitten in the world, beating out four other kittens, two puppies, three toddlers and an amazing duck who feeds the fish. With a whopping 620 slam points, YouTube user emoatali99 was our best connoisseur of cute this week. On the music side, it is no surprise that many of music slam’s top 10 videos were Adele covers. A Whitney Houston cover came out at the top this week, and music slam’s resident expert on talent had more than a thousand slam points. Well done! Check out the rest of the leaderboards for cute slam and music slam.

Can slam-style game mechanics incentivize our users to help improve the ranking of videos -- not just for these five house slams -- but for millions of other search queries and topics on YouTube? Gamification has previously been used to incentivize users to participate in non-game tasks such as image labeling and music tagging. How many votes and voters would we need for slam to do better than the existing ranking algorithm for topic search on YouTube?

As an experiment, we created new slams for a small number of YouTube topics (such as Latte Art Slam and Speed Painting Slam) using existing top 20 videos for these topics as the candidate pool. As we accumulated user votes, we evaluated the resulting YouTube Slam leaderboard for that topic vs the existing ranking on youtube.com/topics (baseline). Note that both the slam leaderboard and the baseline had the same set of videos, just in a different order.

What did we discover? It was no surprise that slam ranking performance had a high variance in the beginning and gradually improved as votes accumulated. We are happy to report that four of five topic slams converged within 1000 votes with a better leaderboard ranking than the existing YouTube topic search. In spite of small number of voters, Slam achieves better ranking partly because of gamification incentives and partly because it is based on machine learning, using:

1. Preference judgement over a pair, not absolute judgement on a single video, and,


2. Active solicitation of user opinion as opposed to passive observation. Due to what is called a “cold start” problem in data modeling, conventional (passive observation) techniques don’t work well on new items with little prior information. For any given topic, Slam’s improvement over the baseline in ranking of the “recent 20” set of videos was in fact better than the improvement in ranking of the “top 20” set.

Demographics and interests of the voters do affect slam leaderboard ranking, especially when the voter pool is small. An example is a Romantic Proposals Slam we featured on Valentine’s day last month. Men thought this proposal during a Kansas City Royals game was the most romantic, although this one where the man pretends to fall off a building came close. On the other hand, women rated this meme proposal in a restaurant as the best, followed by this movie theater proposal.

Encouraged by these results, we will soon be exploring slams for a few thousand topics to evaluate the utility of gamification techniques to YouTube topic search. Here are some of them: Chocolate Brownie, Paper Plane, Bush Flying, Stealth Technology, Stencil Graffiti, Yosemite National Park, and Stealth Technology.

Have fun slamming!

Quantifying comedy on YouTube: why the number of o’s in your LOL matter

Posted by Sanketh Shetty, YouTube Slam Team, Google Research 

In a previous post, we talked about quantification of musical talent using machine learning on acoustic features for YouTube Music Slam. We wondered if we could do the same for funny videos, i.e. answer questions such as: is a video funny, how funny do viewers think it is, and why is it funny? We noticed a few audiovisual patterns across comedy videos on YouTube, such as shaky camera motion or audible laughter, which we can automatically detect. While content-based features worked well for music, identifying humor based on just such features is AI-Complete. Humor preference is subjective, perhaps even more so than musical taste.

 Fortunately, at YouTube, we have more to work with. We focused on videos uploaded in the comedy category. We captured the uploader’s belief in the funniness of their video via features based on title, description and tags. Viewers’ reactions, in the form of comments, further validate a video’s comedic value. To this end we computed more text features based on words associated with amusement in comments. These included (a) sounds associated with laughter such as hahaha, with culture-dependent variants such as hehehe, jajaja, kekeke, (b) web acronyms such as lol, lmao, rofl, (c) funny and synonyms of funny, and (d) emoticons such as :), ;-), xP. We then trained classifiers to identify funny videos and then tell us why they are funny by categorizing them into genres such as “funny pets”, “spoofs or parodies”, “standup”, “pranks”, and “funny commercials”.

 Next we needed an algorithm to rank these funny videos by comedic potential, e.g. is “Charlie bit my finger” funnier than “David after dentist”? Raw viewcount on its own is insufficient as a ranking metric since it is biased by video age and exposure. We noticed that viewers emphasize their reaction to funny videos in several ways: e.g. capitalization (LOL), elongation (loooooool), repetition (lolololol), exclamation (lolllll!!!!!), and combinations thereof. If a user uses an “loooooool” vs an “loool”, does it mean they were more amused? We designed features to quantify the degree of emphasis on words associated with amusement in viewer comments. We then trained a passive-aggressive ranking algorithm using human-annotated pairwise ground truth and a combination of text and audiovisual features. Similar to Music Slam, we used this ranker to populate candidates for human voting for our Comedy Slam.

 So far, more than 75,000 people have cast more than 700,000 votes, making comedy our most popular slam category. Give it a try!

Further reading:

1. “Opinion Mining and Sentiment Analysis,” by Bo Pang and Lillian Lee. 
2. “A Great Catchy Name: Semi-Supervised Recognition of Sarcastic Sentences in Online Product Reviews,” by Oren Tsur, Dmitry Davidov, and Ari Rappoport. 
3. “That’s What She Said: Double Entendre Identification,” by Chloe Kiddon and Yuriy Brun.

Discovering Talented Musicians with Acoustic Analysis

Posted by Charles DuHadway, YouTube Slam Team, Google Research

In an earlier post we talked about the technology behind Instant Mix for Music Beta by Google. Instant Mix uses machine hearing to characterize music attributes such as its timbre, mood and tempo. Today we would like to talk about acoustic and visual analysis -- this time on YouTube. A fundamental part of YouTube's mission is to allow anyone anywhere to showcase their talents -- occasionally leading to life-changing success -- but many talented performers are never discovered. Part of the problem is the sheer volume of videos: forty eight hours of video are uploaded to YouTube every minute (that’s eight years of content every day). We wondered if we could use acoustic analysis and machine learning to pore over these videos and automatically identify talented musicians.

First we analyzed audio and visual features of videos being uploaded. We wanted to find “singing at home” videos -- often correlated with features such as ambient indoor lighting, head-and-shoulders view of a person singing in front of a fixed camera, few instruments and often a single dominant voice. Here’s a sample set of videos we found.



Then we estimated the quality of singing in each video. Our approach is based on acoustic analysis similar to that used by Instant Mix, coupled with a small set of singing quality annotations from human raters. Given these data we used machine learning to build a ranker that predicts if an average listener would like a performance.

While machines are useful for weeding through thousands of not-so-great videos to find potential stars, we know they alone can't pick the next great star. So we turn to YouTube users to help us identify the real hidden gems by playing a voting game called YouTube Slam. We're putting an equal amount of effort into the game itself -- how do people vote? What makes it fun? How do we know when we have a true hit? We're looking forward to your feedback to help us refine this process: give it a try*. You can also check out singer and voter leaderboards. Toggle “All time” to “Last week” to find emerging talent in fresh videos or all-time favorites.

Our “Music Slam” has only been running for a few weeks and we have already found some very talented musicians. Many of the videos have less than 100 views when we find them.

And while we're excited about what we've done with music, there's as much undiscovered potential in almost any subject you can think of. Try our other slams: cute, bizarre, comedy, and dance*. Enjoy!

Related work by Google Researchers:
“Video2Text: Learning to Annotate Video Content”, Hrishikesh Aradhye, George Toderici, Jay Yagnik, ICDM Workshop on Internet Multimedia Mining, 2009.

* Music and dance slams are currently available only in the US.

Auto-Directed Video Stabilization with Robust L1 Optimal Camera Paths

Posted by Matthias Grundmann, Vivek Kwatra, and Irfan Essa, Research Team

Earlier this year, we announced the launch of new features on the YouTube Video Editor, including stabilization for shaky videos, with the ability to preview them in real-time. The core technology behind this feature is detailed in this paper, which will be presented at the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR 2011).

Casually shot videos captured by handheld or mobile cameras suffer from significant amount of shake. Existing in-camera stabilization methods dampen high-frequency jitter but do not suppress low-frequency movements and bounces, such as those observed in videos captured by a walking person. On the other hand, most professionally shot videos usually consist of carefully designed camera configurations, using specialized equipment such as tripods or camera dollies, and employ ease-in and ease-out for transitions. Our goal was to devise a completely automatic method for converting casual shaky footage into more pleasant and professional looking videos.



Our technique mimics the cinematographic principles outlined above by automatically determining the best camera path using a robust optimization technique. The original, shaky camera path is divided into a set of segments, each approximated by either a constant, linear or parabolic motion. Our optimization finds the best of all possible partitions using a computationally efficient and stable algorithm.

To achieve real-time performance on the web, we distribute the computation across multiple machines in the cloud. This enables us to provide users with a real-time preview and interactive control of the stabilized result. Above we provide a video demonstration of how to use this feature on the YouTube Editor. We will also demo this live at Google’s exhibition booth in CVPR 2011.

For further details, please read our paper.

Enhance your productivity with more applications for Google Apps

[Cross-posted from the Google Enterprise Blog]

Last month we launched an improvement that makes more than 60 additional Google services available to Google Apps users. Since the launch, we’ve featured posts from product teams across Google to showcase how you can benefit from the new services.


Our colleagues working on Google Reader, Google Alerts, Google News, and Google Finance described how their products give you new ways to discover content on the web. The Blogger and YouTube teams shared how their services can be used to connect with your customers and communicate information about your products and brand. We also featured posts from the Google Analytics, Google Website Optimizer, Google Custom Search, and Google Translator Toolkit teams to highligh tools that help your company build and optimize your web property. Posts from Google AdWords and Google Places showed how you can make it easier for potential customers to discover your business when they are searching online, and a post from Google Checkout described how you can let visitors purchase products from your site once they arrive. And if your business isn’t built around an online transaction model, the Google AdSense and DoubleClick for Publishers teams outlined tools that you can use to efficiently monetize traffic to your website. We also featured posts on Picasa Web Albums and Google SketchUp & 3D Warehouse that highlighted use cases for sharing and editing photos and 3D images at your organization. Finally, posts from Google Voice and Google Chrome Sync featured products that leverage the power of the web to allow you to work seamlessly across multiple devices, so you’re not tied to your desk phone or desktop PC to be productive.

This series has highlighted a few ways that you can use these additional Google applications, and we’re confident that you will discover many new and interesting use cases that fit your business. You can explore even more exciting Google services now available with your Google Apps account at http://www.google.com/apps/more.

All of these new services can be enabled by your domain administrator from the Google Apps Control Panel at https://www.google.com/a/[your_domain.com] (replace [your_domain.com] with your actual domain name). Your domain administrator can grant different groups of users access to different sets of applications, so your company can get up and running today with more than 60 productivity-boosting applications matched to those users that will benefit from them most.


Posted by Jeremiah Dillon, Google Apps team

Note: Some products may not be available in all areas.

SMB Week Canada Wrap-Up: What’s a Small Business to Do?

Chris O’Neill, Managing Director for Google Canada, recently spoke at the 10th annual Small Business Forum organized by Enterprise Toronto. In his address, he highlighted a few essential steps all small businesses and entrepreneurs should be pursuing to grow their business and reach new customers.

So before you get caught up in the hustle and bustle of the holidays, take the opportunity to make sure you’re using every online tool available to you that can help you make the most of this shopping season. There’s no time like the present to engage in these five things:

• Establish an Online Presence: 20 percent of searches on Google are related to location, so it’s important for local businesses to have a presences on the web. A website does not need to be complex to serve its purpose. Creating a user-friendly, well-structured website will also help search engines like Google find and index it easily. Google Webmaster Tools provides a free and easy way to make your website more Google-friendly.

• Use Free Marketing to Reach Customers: People search Google.com and Google Maps to find local business, so make sure your customers know where you are and what you’re all about by claiming your free Google Places business listing. In addition to sharing your location, phone number and business hours, use Google Places to engage with customers by providing photos, video, coupons, public responses and more. You can also take advantage of free marketing opportunities by posting content to social networking sites, such as YouTube.

• Know Your Customers: To understand why some visitors aren’t converting, get website analytics data and learn what potential customers are doing on your site. Google Analytics is one of these analytics products, and it’s a free and powerful tool that can help you answer questions about the effectiveness of your content, how engaged your users are with your site, where they abandon your shopping cart and much more. With the right data in your hands, you can make smarter website design decisions and also make sure that the money you spend on advertising is actually delivering the results you want.

• Advertise Online: Online advertising is targeted, measurable and flexible. Products such as Google AdWords allow business owners like you to connect with your target audience at the exact moment they search for your products or services online. With AdWords, you only pay when someone clicks on your ad is taken directly to your website. You also get actionable analysis and performance information, so you know how to refine your ad copy or the keywords that trigger your ad to appear on the search results page. Plus, any business can be up and running in 15 minutes.
• To find out about all our advertising tools and products, visit our Google for Advertisers site for Canadian businesses.

• Embrace the Cloud: Web-based applications, such as Google Apps, are helping to streamline productivity and ensure that your business is running efficiently. Your employees can collaborate on documents in real-time and access them from anywhere, whether they’re on the road or at the office. This suite of online products also helps businesses spend less time and money managing email and other IT services, giving them the ability to focus more on what they do best: creating quality products and services, and sharing them with customers. Best of all, you can get started with Google Apps for free!

Posted by Andrew Swartz, Small Business Blog team

YouTube’s Promoted Videos picks up steam

How do you increase sales and build your brand when you’re on a limited budget? You might consider using YouTube’s Promoted Videos. YouTube reports that it has served its 500,000,000th Promoted Video view this week and has seen a six-fold increase in clicks it has delivered to businesses such as Shopper’s Choice, Dynomighty and Orabrush. This ad product combines the branding capabilities of video with the direct response action of search advertising, allowing advertisers to promote their videos against search results or related videos on YouTube. For more information on this announcement, please visit the YouTube blog for the full story.

Posted by the YouTube Team

Revenue grows 48% with help from YouTube videos

Editors note: Today’s guest bloggers are Troy Olson, Digital Advertising Manager, and Jeff Loquist, Search Marketing Manager, for ShoppersChoice.com. ShoppersChoice.com owns and operates a family of web stores with a wide selection of products, from barbecue grills and accessories to patio sets.

With the tagline, “we smoke the competition,” BBQ Guys has built a hot business around home furniture, fireplaces, and kitchen cookware – but the company’s true passion is barbecuing and grills. We’ve created our own YouTube channel around all things related to outdoor cooking, from recipe how-tos to grill reviews. For us, YouTube has been a recipe for success. Visit the YouTube blog to learn more about how we’ve used Google tools to build a fun, rewarding small business.

Posted by Serena Satyasai, The YouTube Team

Event recap: How to run a successful social campaign

[Cross posted from the AdWords Agency Blog.]

Last week, YouTube and SEMPO hosted a social marketing panel, "How to run a successful social campaign," for SEMPO's San Francisco and Los Angeles working groups. The panel featured speakers from YouTube, Facebook, Twitter, and Athena East, and highlighted the unique products available to marketers, and best practices for executing measurable, impactful social advertising strategies.

Derek Gordon of Yield Software was there, and shared what he learned in today's Mediapost Search Insider column.

Click here for his complete update.

Posted by AgencyAd Solutions Blog Team

Broadcast your business through the TV for All Contest

[Cross-posted from Inside AdWords]

Today we’re announcing the second annual TV for All contest, where your business has the opportunity to win $25,000 in national advertising with Google TV Ads and online video partner sites, including YouTube.

click for a full size image

We originally launched this contest last year and received nearly 250 submissions. Three winners, including Owners.com, won free TV media through Google and successfully extended their brands across the nation.

“It’s always exciting to see what other marketers think of your work,” says George Karavaras of Owners.com about why the company entered TV for All in 2009. The best part, he says, is that “it doesn’t take a lot of time or money to create a high impact TV ad through Google’s creative network.”

click for full size image

Now it’s your turn! Entering is easy: simply create a video ad for your business, upload it to YouTube and submit it to our TV for All YouTube Channel between September 15th and October 12th. If you don't have a video ad or the tools to create one, professional tools by SpotMixer will be available for free to help you make a polished ad in just minutes.

Three winners whose ads best exemplify creativity and a compelling message will receive $25K, $15K, or $10K in national TV and online video advertising using Google AdWords.

If you've never promoted your business using TV and video, the TV for All contest is your chance to get started. For more details and to enter the contest, visit www.youtube.com/tvforall.

Posted by Nathania Lozada, Inside AdWords crew