A Windows Phone app for the Nokia Lumia 1020 brings a Waterloo Student and MSP first place in Denmark!

Rudi Chen, a Microsoft Student Partner and student at Waterloo University, recently won the Nokia Future Capture Contest beating out developers from all over the world. We asked Rudi to tell us a bit about his experience.

August 2013: Ten finalist teams are chosen from thousands of entries from all across the world. These people get to go to Sweden for a 27-hour Hackathon – the Nokia Future Capture contest. The prize? A brand new Lumia 1020, with a 41-megapixel camera that eclipses all other smartphones. Coding. Judging. And finally, a victory.

Yet for me, the story begins a little earlier.

The Idea

Five years ago, I was avidly looking at soon-to-be released Photoshop CS4’s new features. One in particular stood out: content-aware scaling. It made it possible to change an image’s aspect ratio without distorting its content. The algorithm somehow “knew” what was in the scene and what could safely be taken out. Watching the demo video was like watching a magic show. What kind of technology could allow such a thing?

Then, a few months ago, while passively walking out at the end of a statistics class, I glanced at a group of student gathered around a laptop with a PDF file open. It was a paper called “Seam Carving for Content-Aware Image Resizing”. At that moment I thought, wouldn’t it be cool to write an app that implements this feature? By now, I had gathered enough programing experience and the algorithm no longer appeared to be magic – it was a simple, neat technique that I could understand and implement.

Finally, in July, Nokia announces Future Capture. This was exciting - a Hackathon with imaging as a main theme was the perfect opportunity to give Seam Carving a shot. The idea is to allow users to change the aspect ratio of their pictures (namely to 1:1 instagram-size) without distortions to the content of the picture, and downsample 41 MP images while amplifying the salient features, by removing the least important bits first, such as the background.

I knew that I couldn’t make a full app in a mere two days without some assistance, so I teamed up with long-time friend Shida Li for this Hackathon.

The process

The first challenge was to figure out how to implement the algorithm on a mobile device. Although mobile chip manufacturers have done a great job designing speedy low-power processors for smartphones, the processors are still, well, low-power. In addition, multi-tasking on mobile devices is much more limited. The user can’t easily switch between apps while waiting for computation finish, so we must be able to analyze the entire image within a few seconds.

The original paper could not accomplish this even on a desktop, but I found a follow-up paper, “Real-Time Content-Aware Image Resizing”, that could. So I wrote the algorithm early on. It was allowed and after all, this wasn’t something we could improvise once in Sweden. No algorithm, no app. In version 1 on a regular Ultrabook with the WP8 emulator, I got 1.2 seconds for preprocessing, 10 fps while resizing the image. Reasonable.

The Phone

On August 29, we depart for Lund. Passing through Amsterdam and Copenhagen, we finally arrive on the morning of the next day. An enthusiastic greeter from Nokia await us at the airport. He has two Lumia 1020 for us to play with. Already from the first few pictures, we can see the device lives up to the hype.

It seems trendy nowadays to take pictures of meals, so it seems natural to do the same with the Lumia 1020.

This rivals every point-and-shoot I’ve ever used.

The event

After a visit of Lund, we get back to the hotel, where we oversleep in the evening (good ol’ jet lag). It is not until 11 PM that I finally meet with Shida to plan out what the actual app will look like.

I couldn’t previously test the algorithm on my HTC 8S, as it didn’t have enough RAM to support the memory-intensive process involved in analyzing the least important bits of the image. With the Lumia 1020’s 2 GB of ram, I could.

The unexpected problem

That’s when I realized that ARM processors were even slower than expected. 10 seconds of preprocessing for a 1 MP image, 1 FPS while resizing. Yikes. We needed to change our plans a little, focusing mainly on resizing smaller images.

The Hackathon started the next morning at 9 AM. My first order of priority was to benchmark all the different components of the Seam Carving algorithm and figure out the bottlenecks. Speed was really critical for a good user experience, so I decided to cut on some memory optimization (dropping support for larger images) for a few extra FPS. In the meantime, Shida created the basic structure of the app, from taking pictures with the camera to navigating between pages to creating a “paint” mode where the user can manually specify which parts of the images the resizing algorithm is not allowed to touch.

To get a sufficient speed, I knew it wouldn’t be enough to minimize the number of instructions the algorithm uses from a high-level perspective. It was necessary to optimize what was happening inside the CPU. Using SIMD instructions with NEON was an attractive option, but creating a C++ component to interop with C# was a bit risky in the limited timeframe of the Hackathon.

Instead, I looked for ways to make array accesses use the CPU cache as efficiently as possible. Using jagged array instead of 2d rectangular arrays to hold our image data gave a 1.5-2x speedup, which was quite nice. For the initial analysis of the image, which involves a convolution, caching some computation and processing only one row of the array at the time to stay in the same cache line gave a 5-6x speedup in that section. This really shows how much time the CPU spend on moving data in and out of memory – I concept I learned from Microsoft’s own Herb Sutter when he gave a talk on latency.

The long haul

As the day progressed, more and more features were added onto the app. Shida implemented filters using Nokia’s SDK, which is pretty nice (I can’t image how long it would take to write all those filters manually). Nothing was without hiccups of course. Compilation issues due to imported packages caused a fair amount of downtime and we weren’t very familiar with Visual Studio 2013’s Git with TFS features that we were using to share our work. Luckily, we didn’t run into issues that ate up too much time, unlike some other teams.

During the night, we found that we were surprisingly not that tired. Adrenaline can do wonders, I suppose. It seemed to have been the same for all other teams – I don’t think anyone bothered taking naps more than a few minutes long. By around 6 AM though, productivity was down severely. Red Bull didn’t seem to have much of an effect either. On the bright side, we at least had a Minimum Viable Product that we could show, despite being rough around the edges.

Teams still working hard as the sun rises. A lot of the organizers and Nokia’s dev team also stayed during the night.

The deadline

Noon of the second day was the deadline for our entry submission. Then came lunch, the pitches, and judging. By then, we were quite happy with our work and our confidence was rising. However, regardless of confidence level, winning first-place is always a surprise. Especially with the awesome ideas other teams had made. This isn’t just polite winner-speech – I genuinely would want to use some of the other team’s apps and there were ideas with more business potential than ours. What made the difference (for the judges, at least), boiled down to implementation. Our app worked exactly as it should.

Following that, we pretty much slept from the afternoon to the morning of the next day.

Downtime

As we wouldn’t get a chance to go to Europe again for quite a while, we spent a day sightseeing in Copenhagen. It was a good opportunity to use the awesome Lumia cameraphone (and in Shida’s case, his DSLR, which made for interesting comparison shots between the two).

I think Copenhagen is the only place in the world where LEGO stores outnumber Starbucks.

The full resolution of this panorama shot is 21277x7506 – a mindboggling 160 megapixels.

The night is when the Lumia 1020 begins showing its superpowers. This picture wasn’t taken with a tripod.

Macro photography is very fun, a feature unique to the Lumia 1020.

And that was my 4-day trip to Sweden, courtesy of Nokia’s awesome team. Look forward for the app to be published!