September 19, 2015

Understanding an Exciting New Feature of HEVC: Tiles

As an editor of the IEEE R-letter, I write every now and then some short "letters" (one page long easy-going text) about a recent research article that I found especially interesting. I think it is appropriate to have also these letters put in this blog. Thus, I will publish them also here.

The paper I'd like to emphasize is:
Kiran Misra, Andrew Segall, Michael Horowitz, Shilin Xu, Arild Fuldseth, and Minhua Zhou, “An Overview of Tiles in HEVC”, IEEE Journal of Selected Topics in Signal Processing, Vol. 7, No 6, December 2013

The High Efficiency Video Coding (HEVC) standard significantly improves coding efficiency (gains reported as 50% when compared to the state-of-the-art MPEG-4 AVC H264), and thus is expected to become popular despite the increase in computational complexity. HEVC also provides various new features, which can be exploited to improve the delivery of multimedia systems. Among them, the concept of tiles is in my opinion a promising novelty that is worth attention. The paper "An Overview of Tiles in HEVC" provides an excellent introduction to this concept.

The goal of a video decoder (respectively encoder) is to convert a video bit-stream (respectively the original sequence of arrays of pixel values) into a sequence of arrays of pixel values (respectively a bit-stream). The main idea that is now adopted in video compression is the hierarchical structure of video stream data. The bit-stream is cut into independent Group of Pictures (GOP), each GOP being cut into frames, which have temporal dependencies with regards to their types: Intra (I), Predicted (P) or Bidirectional (B) pictures. Finally, each frame is cut into independent sets of macroblocks, called slices in the previous encoders.

The novelty brought by HEVC is the concept of tile, which is at the same "level" as slice in the hierarchical structure of video stream data.

The motivations for both slices and tiles are, at least, twofold: error concealment and parallel computing. First, having an independently parsable unit within a frame can break the propagation of errors. Indeed, due to the causal dependency between frames, an error in a frame can make the decoder unable to process a significant portion of the frames occurring after the loss event. Slices and tiles limit, at least from a spatial perspective, the propagation of an error on the whole frame. Second, the complexity of recent video and the requirements of high-speed CPU speed (which unfortunately requires power and generates heat) can be partially addressed by parallelizing the decoding computation task across multiples computing units, regardless of whether these are cores in many-cores architectures or computing units in Graphics Processing Units (GPUs). The independency of slides and tiles is expected to facilitate the implementation of video decoder on parallel architectures.

Unfortunately, the concept of slices suffers in practice from serious weaknesses, which tiles are expected to fix.

In the paper, the authors introduce the main differences between tiles and slices, which are two concepts that, at a first glance, can be confused. They focus on the motivation for parallel computation.

The first part of the paper explains in details the main principles between both approaches, in particular the fact that tiles are aligned with the boundaries of Coded Tree Blocks (CTD), which provides more flexibility to the partitioning. This brings several benefits: a tile is more compact, which leads to a better correlation between pixels within a tile when compared to the correlation between pixels in a slice. Tiles also require less headers, among other advantages.

The authors also introduce the known constraints to be taken into account when one wants to use tiles today. The whole Section 3 is about the tile proposal in HEVC, and the main challenges to be addressed for a wide adoption. Next, the authors present some examples when tiles are useful. Both parts are written so that somebody being just familiar with the concepts can understand both the limitations behind the concept of tiles and how these weaknesses have been addressed in practice.

The last part of the paper, in Section 5, deals with some experiments, which demonstrate the efficacy of HEVC for lightweight bit-streams and parallel architectures. At first authors assess the parallelization and the sensibility of network parameters, including the Maximum Transmission Unit (MTU), on the performances of slices versus tiles. They finally measure the performances of stream rewriting for both approaches.

In short, the paper shows that tiles appear to be more efficient than slices on a number of aspects. The paper proposes a rigorous, in-depth, introduction of the main advantages of tiles. This can foster research on the integration of tiles into next-generation multimedia delivery systems.

September 2, 2015

Uploading innovative engineers: 15 years remaining

Four years ago, I wrote an outrageous post about how "un-geek" are French engineers in average. Since 2011, many things have changed in France: code is expected to be (soon) taught in elementary schools, successful geek entrepreneurs are in the spotlight, geek-ish schools and co-working hacker spaces flourish, ... It will take time, but, hopefully, France in 2025 will be geek-friendly. Now, what about innovation?

Entrepreneurship has become a cause nationale in France, with a lot of initiatives and announcements. Analysts try to decipher the structural problems regarding innovation in France, in particular an excellent study (in french) about innovation "ecosystems" was released yesterday. Everything said in this article is 100% true... but it misses a point: how "un-innovative" are the French higher-educated people in average.

As a teacher in a high-education engineering school, I have headed an "Innovation & Entrepreneurship" course for 8 years (with some success stories here and there). Every student must follow this course. From my experience of teaching this innovation course to around 180 students every year, I can just recall that the average higher-educated students (usually coming from Classes Préparatoires) struggle to:
  • Deal with uncertainties. The most brilliant scientific students are those who excel at finding solutions to problems. But what about when there is no clearly identified problem? And what about when any solution to a problem has its pros and cons? Most of the students who would have not enrolled in an Entrepreneurship program if they had the choice are very uncomfortable with uncertainties. They are the right targets for innovation mindset re-formatting.
  • Convince. The French education system does not include any training in talking, debating, arguing, more generally communication skills. When every US kid should defend a point in a science fair, the same age French kids are taught how to raise the hand before talking, the quieter the better. Oral debates barely exist at french school. As a matter of fact, it is frequent that students give their very first "public" talk when they are 20 years old. Teaching the art of pitching is necessary for every student.
  • Accept being a failure and a rebel. This is especially true during brainstorming and creativity sessions where it is common that somebody, say Jo, suggests a high-risk or out-of-the-box idea but almost immediately the fear of being judged makes Jo himself overturn his own damned idea. I'd love to put Jo in more creativity training sessions so that he becomes self-confident enough.
The percentage of engineers who have these three core competencies (an innovation-friendly mindset) in 2015 is as low as the percentage of engineers who had a geek-friendly mindset in 2011. Solutions like super-hyped incubators or  state-owned VCs are right but they are similar to providing xDSL broadband connections to geeks in 2000s. It is cool for the happy fews, but it does not change the mindset of the others.

In my opinion, a successful innovation ecosystem is such that everybody in the society (especially every higher-educated worker) has an innovation-friendly mindset. Everybody means here people who do not aim to become entrepreneur and even those who are not directly related to innovation. No society can afford that a majority of higher-educated people have not developed in particular these three key competencies at school. The structural reasons behind this failure for average higher-educated workers are in my opinion more critical than an imperfect innovative ecosystem for a tiny fraction of innovators. Indeed, the lack of inclinations toward uncertainties, communication skills and rebel-attitude is a transmissible disease for any innovative ecosystem.

It is the mission of teachers in high-education institutions to fight the stigmata of twenty years of un-innovative mindset formatting. The special "Entrepreneurship" programs that are commonly offered in other higher-education institutions (or in online courses) do not contribute to this mission because these programs enroll volunteering students who have already overcome their innovation-related mindset limitations. These students are not the right target. To set up a profoundly innovation-friendly ecosystem in 2030, we have to train all higher-educated students now so that innovation will be pervasive in the society, especially at schools, in community groups and in the traditional companies. Hopefully, the ecosystem will then be friendly to entrepreneurs...