Algorithms and advanced methods for video coding in large scale systems

Abstract

The new era of 4K and 8K (UHD) resolutions cameras and TV sets emerged from the ever increasing demands for higher video resolution. Video is by far the "biggest" Big Data, stretching network and storage capacity to their limits. In order to handle this situation, video compression has been an active field of study for many years, producing output of huge commercial interest. One of the most successful and widely used video coding standards is H.264/AVC. Even if H.264/AVC was a wide marketing success, its weaknesses and limitations in tacking UHD resolutions were made apparent relatively early. For this reason, new video coding standards were launched as successors to H.264/AVC. The most eminent examples of the new generation video coding standards are the High Efficiency Video Coding (HEVC), the recently launched AV1 and the currently developing Versatile Video Coding (VVC). Each one of the video coding standards was designed with the primary target of outperforming the prior state of the art standards. Therefore, each newcomer introduced new coding tools that increases computational complexity both at the encoder and at the decoder side, and trade-off mechanisms between complexity and compression efficiency were presented at the design steps of every standard. Both the high resolution demands and the increased computational complexity of video coding standards, result to time consuming and resource demanding tasks. Harnessing the high computational demands is done by exploiting parallelization at various levels. In this thesis, we tackle both of the aforementioned aspects, namely, harnessing computational overhead through parallelism and exploiting the potential of resource consumption reduction at a high scale. Concerning the first aspect (parallelism), we focus on a block level coarse grained parallel approaches, which split a frame into groups of blocks and consider each group as an independent task. In particular, tile partitioning is considered whereby a frame is split into horizontal and vertical zones, the intersections of which form tiles. We propose and evaluate algorithms that define tile partitions under various scenarios with the aim of balancing the resulting load in the available processors. Concerning resource consumption reduction at a high scale, the improved compression ratio achieved by HEVC, compared to H.264/AVC, is the key enabling factor. Furthermore, we tackle issues related to H.264/AVC-HEVC transcoding. Towards this aspect, two paths are explored. In the first path, we propose a method for estimating regions of high complexity within a frame, based on information that can be extracted from H.264/AVC headers. Such information is important in the case of a parallel transcoder, as it can be used for efficient load balancing. In the second path, we tackle the problem of scheduling transcoding processes at a massive scale so as to maximize resource benefits while minimizing operational costs.

Η νέα εποχή με κάμερες και τηλεοράσεις υψηλής, 4K και 8K (UHD), ανάλυσης προέκυψε από τις ολοένα αυξανόμενες απαιτήσεις για υψηλότερης ανάλυσης βίντεο. Το βίντεο είναι μακράν το "μεγαλύτερο" Big Data, οδηγώντας σε εκτεταμένη χρήση του δικτύου και σε σημαντικά μεγάλη δέσμευση της χωρητικότητας αποθήκευσης. Για την αντιμετώπιση αυτής της κατάστασης, η συμπίεση βίντεο αποτελεί ενεργό πεδίο μελέτης εδώ και πολλά χρόνια και παράγοντας τεράστιου εμπορικού ενδιαφέροντος. Ένα από τα πιο επιτυχημένα και ευρέως χρησιμοποιούμενα πρότυπα κωδικοποίησης βίντεο είναι το H.264/AVC. Ενώ το H.264/AVC είναι αρκετά επιτυχημένο, οι αδυναμίες και οι περιορισμοί του στην αντιμετώπιση των αναλύσεων UHD έγιναν εμφανείς σχετικά νωρίς. Για αυτόν τον λόγο, ξεκίνησαν νέα πρότυπα κωδικοποίησης βίντεο ως διάδοχοι του H.264/AVC. Τα πιο επιφανή παραδείγματα των προτύπων κωδικοποίησης βίντεο νέας γενιάς είναι το High Efficiency Video Coding (HEVC), το AV1 που ολοκληρώθηκε πρόσφατα και το τώρα αναπτυσσόμενο Versatile Video Coding (VVC). Κάθε ένα από τα νέα πρότυπα κωδικοποίησης βίντεο σχεδιάστηκε με πρωταρχικό στόχο να ξεπεράσει τα προηγούμενα πρότυπα καλύπτοντας τις υπάρχουσες ανάγκες που έχουν προκύψει. Επομένως, κάθε νέο πρότυπο εισήγαγε νέα εργαλεία κωδικοποίησης που αυξάνουν την υπολογιστική πολυπλοκότητα τόσο στην πλευρά του κωδικοποιητή όσο και σε αυτήν του αποκωδικοποιητή. Επίσης υπήρξε συμβιβασμός μεταξύ πολυπλοκότητας και αποτελεσματικότητας συμπίεσης στα στάδια σχεδιασμού του κάθε προτύπου. Τόσο οι απαιτήσεις υψηλής ανάλυσης όσο και η αυξημένη υπολογιστική πολυπλοκότητα των προτύπων κωδικοποίησης βίντεο, οδηγούν σε χρονοβόρες εργασίες και απαιτούν σημαντικούς πόρους ενός υπολογιστικού συστήματος. Η αξιοποίηση των υψηλών υπολογιστικών απαιτήσεων γίνεται με την εκμετάλλευση του παραλληλισμού σε διάφορα επίπεδα. Σε αυτήν τη διατριβή αντιμετωπίζουμε και τις δύο από τις προαναφερθείσες πτυχές, δηλαδή την αξιοποίηση των υπολογιστικών πόρων μέσω του παραλληλισμού και την πιθανή μείωση της κατανάλωσης πόρων σε συστήματα μεγάλης κλίμακας. Όσον αφορά την πρώτη πτυχή (παραλληλισμός), εστιάζουμε σε επίπεδο μπλοκ, coarse grain παράλληλες προσεγγίσεις, οι οποίες χωρίζουν μια εικόνα σε ομάδες από μπλοκ και θεωρούν κάθε ομάδα ως ανεξάρτητη εργασία. Συγκεκριμένα στη μέθοδο τμηματοποίησης που ονομάζεται tile partitioning, θεωρείται ότι μία εικόνα χωρίζεται σε οριζόντιες και κατακόρυφες ζώνες τα σημεία τομής των οποίων σχηματίζουν τα επωνομαζόμενα tiles. Προτείνουμε και αξιολογούμε αλγόριθμους που ορίζουν την τμηματοποίηση των tiles χρησιμοποιώντας διάφορα σενάρια με σκοπό την εξισορρόπηση του φόρτου που προκύπτει στους επεξεργαστές. Όσον αφορά τη μείωση της κατανάλωσης των πόρων σε υψηλής κλίμακας συστήματα, η μεγαλύτερη συμπίεση που επιτυγχάνεται από το HEVC σε σύγκριση με το H.264/AVC είναι ο βασικός παράγοντας που επιλέχθηκε η χρήση του. Επίσης αντιμετωπίζουμε ζητήματα που σχετίζονται με τη διακωδικοποίηση (transcoding) μεταξύ του H.264/AVC και του HEVC. Ως προς αυτή την κατεύθυνση εξετάζονται δύο μονοπάτια. Στο πρώτο προτείνουμε μια μέθοδο για την εκτίμηση περιοχών υψηλής πολυπλοκότητας μέσα σε μία εικόνα, βάσει των πληροφοριών που μπορούν να εξαχθούν από το προηγούμενο πρότυπο (H.264/AVC). Αυτές οι πληροφορίες είναι σημαντικές στην περίπτωση ενός παράλληλου transcoder, καθώς μπορούν να χρησιμοποιηθούν για την αποτελεσματική εξισορρόπηση του φόρτου εργασίας των επεξεργαστών. Στο δεύτερο μονοπάτι αντιμετωπίζουμε το πρόβλημα του προγραμματισμού διεργασιών διακωδικοποίησης σε μαζική κλίμακα, ώστε να μεγιστοποιήσουμε τα οφέλη των δεσμευμένων υπολογιστικών πόρων, ελαχιστοποιώντας ταυτόχρονα το λειτουργικό τους κόστος.