Luís Filipe Rosário Lucas Eduardo Antônio Barros da Silva Sérgio Manuel Maciel de Faria Nuno Miguel Morais Rodrigues Carla Liberal Pagliari Effi cient Predictive Algorithms for Image Compression Efficient Predictive Algorithms for Image Compression Luís Filipe Rosário Lucas Eduardo Antônio Barros da Silva Sérgio Manuel Maciel de Faria Nuno Miguel Morais Rodrigues Carla Liberal Pagliari Efficient Predictive Algorithms for Image Compression 123 LuísFilipeRosárioLucas EduardoAntônioBarrosdaSilva InstitutodeTelecomunicações ProgramadeEngenhariaElétrica ESTG–InstitutoPolitécnicodeLeiria UniversidadeFederaldoRiodeJaneiro Leiria,Portugal RiodeJaneiro,Brazil SérgioManuelMacieldeFaria NunoMiguelMoraisRodrigues InstitutodeTelecomunicações InstitutodeTelecomunicações ESTG–InstitutoPolitécnicodeLeiria ESTG–InstitutoPolitécnicodeLeiria Leiria,Portugal Leiria,Portugal CarlaLiberalPagliari DepartamentodeEngenhariaElétrica(SE/3) InstitutoMilitardeEngenharia Urca-RiodeJaneiro,Brazil ISBN978-3-319-51179-5 ISBN978-3-319-51180-1 (eBook) DOI10.1007/978-3-319-51180-1 LibraryofCongressControlNumber:2016961282 ©SpringerInternationalPublishingSwitzerland2017 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictional claimsinpublishedmapsandinstitutionalaffiliations. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Contents 1 Introduction .................................................................. 1 1.1 Motivation .............................................................. 1 1.2 ObjectivesandContributionsoftheBook ............................ 3 1.3 OutlineoftheBook .................................................... 5 2 PredictionTechniquesforImageandVideoCoding..................... 7 2.1 DigitalVideoRepresentation .......................................... 7 2.2 ImagePredictionOverview............................................ 9 2.3 State-of-the-ArtPredictionMethods .................................. 13 2.3.1 Intra-FramePrediction......................................... 13 2.3.2 Inter-FramePrediction......................................... 17 2.4 Least-SquaresPredictionMethods .................................... 20 2.4.1 LinearPredictionofImagesandVideoUsingLSP .......... 21 2.4.2 Context-BasedAdaptiveLSP.................................. 22 2.4.3 Block-BasedLSP .............................................. 23 2.4.4 Spatio-TemporalLSP.......................................... 24 2.5 SparseRepresentationforImagePrediction .......................... 25 2.5.1 SparsePredictionProblemFormulation ...................... 26 2.5.2 MatchingPursuitMethods..................................... 28 2.5.3 TemplateMatchingAlgorithm ................................ 29 2.5.4 NeighbourEmbeddingMethods............................... 30 2.6 Conclusions............................................................. 33 3 ImageandVideoCodingStandards....................................... 35 3.1 HybridVideoCompression............................................ 35 3.2 Compressionof2DVideo.............................................. 37 3.2.1 H.265/HEVCStandard......................................... 38 3.2.2 ExperimentalResults .......................................... 46 3.3 Compressionof3DVideo.............................................. 49 3.3.1 3DVideoSystems.............................................. 49 v vi Contents 3.3.2 3DVideoCodingStandards................................... 58 3.3.3 ExperimentalResults .......................................... 61 3.4 Conclusions............................................................. 64 4 CompressionofDepthMapsUsingPredictiveCoding .................. 65 4.1 OverviewofIntraTechniquesforDepthMapCoding................ 66 4.1.1 DirectionalIntraPrediction.................................... 67 4.1.2 DepthModellingModes....................................... 68 4.1.3 DepthLookupTable ........................................... 69 4.1.4 Segment-WiseDCCoding..................................... 69 4.1.5 SingleDepthIntraMode....................................... 70 4.1.6 ViewSynthesisOptimisation.................................. 70 4.2 OverviewofPredictiveDepthCoding................................. 71 4.3 CodingTechniquesofPDCAlgorithm................................ 73 4.3.1 FlexibleBlockPartitioning.................................... 73 4.3.2 DirectionalIntraPredictionFramework ...................... 75 4.3.3 ConstrainedDepthModellingMode.......................... 77 4.3.4 ResidualSignalCoding........................................ 79 4.3.5 BitstreamSyntaxandContextModelling..................... 81 4.4 PDCEncoderControl.................................................. 83 4.5 ExperimentalResults................................................... 84 4.5.1 EvaluationofPDCAlgorithmforIntraCoding .............. 85 4.5.2 EvaluationofPDCAlgorithmUsingVSOMetric ........... 91 4.5.3 Evaluation of PDC Algorithm Combined with3D-HEVCStandard ...................................... 93 4.6 Conclusions............................................................. 95 5 SparseRepresentationMethodsforImagePrediction................... 97 5.1 3DHoloscopicImageCodingUsingLLE-BasedPrediction......... 98 5.1.1 ProposedHEVCEncoderUsingLLE-BasedPrediction..... 99 5.1.2 ExperimentalResults .......................................... 101 5.2 TheSparse-LSPMethodforIntraPrediction ......................... 104 5.2.1 AlgorithmDescription......................................... 105 5.2.2 MathematicalInterpretation ................................... 107 5.3 ApplicationofSparse-LSPtoHEVCStandard....................... 109 5.3.1 ImplementationDetails........................................ 110 5.3.2 ExperimentalResults .......................................... 111 5.4 Conclusions............................................................. 115 6 GeneralisedOptimalSparsePredictors................................... 117 6.1 Two-StageInterpretationofDirectionalPrediction................... 118 6.2 GeneralisingDirectionalPrediction................................... 122 6.3 SparseModelEstimationAlgorithms ................................. 124 6.3.1 MatchingPursuitAlgorithms.................................. 125 6.3.2 LeastAngleRegression........................................ 125 6.3.3 LASSORegression ............................................ 126 6.3.4 ElasticNetRegression......................................... 127 Contents vii 6.4 Proposed Algorithm Based on Adaptive Sparse PredictorsforHEVC................................................... 128 6.5 ExperimentalResults................................................... 130 6.5.1 EffectofSparsityConstraints ................................. 131 6.5.2 RegularisationParametersforOptimalRDPerformance.... 133 6.5.3 RD Performance Relative to Other Intra PredictionMethods ............................................ 140 6.6 Conclusions............................................................. 143 7 ConclusionsandOtherResearchDirections.............................. 145 A TestSignals ................................................................... 149 A.1 TestImages ............................................................. 149 A.2 HoloscopicImages ..................................................... 153 References......................................................................... 157 Index............................................................................... 165 List of Figures Fig.2.1 DPCMblockdiagramforlossyimagecompression ............... 10 Fig.2.2 Spatialpredictioninarasterscanorderencoder,e.g. DPCM ................................................................ 10 Fig.2.3 Blockdiagramforagenerictransform-basedhybrid videocompressionsystem .......................................... 12 Fig.2.4 Available neighbouring regions used by intra predictionmodesinHEVCstandard ............................... 14 Fig.2.5 IntrapredictionangularmodesusedinHEVCstandard ........... 15 Fig.2.6 SpatialcandidatesofmotioninformationforMerge mode ................................................................. 19 Fig.2.7 LSPfiltercontext(pixelsrepresentedbywhitecircles) andassociatedtrainingwindow ..................................... 22 Fig.2.8 Exampleofa13thorderspatio-temporalfiltercontext usingcausalneighboursfromthecurrentframe(spatial neighbours)andpreviousencodedframe(temporal neighbours) .......................................................... 25 Fig.2.9 Approximationsupport(template)andsearchwindow used in sparse coding and neighbour-embedding methods .............................................................. 26 Fig.3.1 ArchitectureofHEVCalgorithm ................................... 38 Fig.3.2 Partitioningmodesofaninter-codedCBintoPBs ................ 40 Fig.3.3 SearchwindowusedbyIBC(representedbygray CTUs) ................................................................ 45 Fig.3.4 Usedtestimages:Barbara(512(cid:2)512)(left,a)and Poznan Street, camera 4, frame 0 (1920(cid:2)1088) (right,b) ............................................................. 47 Fig.3.5 Rate-distortionperformanceofHEVCandH.264for testimages(a)Barbaraand(b)PoznanStreet,camera 4,frame0 ............................................................ 48 ix x ListofFigures Fig.3.6 Rate-distortionperformanceofHEVCandH.264for testvideosequences(a)RaceHorses(classC)and(b) BasketballDrive(classB) .......................................... 50 Fig.3.7 Frame-compatibleformatsforstereovideo:topimages representanexampleofastereopair;bottomimages representtheside-by-sideandtop-bottomformatsof thegivenstereopair ................................................. 52 Fig.3.8 ExampleofMVDformatusingthreetexturevideo views(left)andthreedepthmapviews(right) ..................... 54 Fig.3.9 A3Dholoscopicimagingsystem [57]:(a)acquisition side;(b)displayside ................................................ 57 Fig.3.10 Holoscopic image captured with a 250(cid:2)m pitch micro-lensarray:(a)fullimagewithresolutionof 1920(cid:2)1088;(b)enlargementof196(cid:2)140pixels showingthemicro-images .......................................... 57 Fig.3.11 Prediction dependencies in 3D-HEVC standard for multiview video coding: inter-viewprediction is represented solid arrows and inter-component predictionisrepresentedbydottedarrows ......................... 59 Fig.3.12 Rate-distortionperformanceofsharktestsequence usingthe3D-HEVC,3D-HEVCwithoutVSOand theMV-HEVC configurations: (a)average PSNR oftextureviewsversusbitrateoftextureviews(b) averagePSNRofsynthesisedviewsversusbitrateof depthmaps ........................................................... 63 Fig.4.1 ExampleofWedgelet(left)andContour(right)block partitions ............................................................. 68 Fig.4.2 SVDC procedure for the distorted depth block identified in bottom depth map (labelled by testedblock) ......................................................... 70 Fig.4.3 Blockdiagramoftheintra-basedPDCalgorithm .................. 72 Fig.4.4 Possible block sizes in PDC and respective label numbers .............................................................. 74 Fig.4.5 Example of an optimal block partitioning and correspondingsegmentationtreeinPDCalgorithm usingquadtreeplusrecursiveflexiblepartitioning ................. 74 Fig.4.6 Exampleofeasytopredictedges(leftandmiddle)and adifficulttopredictedge(right) .................................... 77 Fig.4.7 BlockpartitionexamplesusingCDMM ............................ 78 Fig.4.8 DifferentCDMMpartitionslopesprovidedbyflexible partitioning ........................................................... 78 Fig.4.9 DetailedschematicofthePDCresiduecodingmethod ........... 80 ListofFigures xi Fig.4.10 Detail of the third virtual view (vv3) of Poznan Street (frame 0) synthesised using (a) reference uncompresseddepthmaps,(b)3D-HEVC(RefHTM) encodeddepthmapsand(c)PDCencodeddepthmaps, forrate-distortionpoint3(p3) ...................................... 89 Fig.4.11 AveragepredictionmodeusageinPDCalgorithmfor alltestedlambdasandencodedviewsofeachtest sequence ............................................................. 91 Fig.4.12 AverageBDRATEvaluesofPDCalgorithmusing SSEandVSOdistortionmetricsrelativeto3D-HEVC usingRefHTM andRefHTMCVSOconfigurations, respectively .......................................................... 92 Fig.4.13 AverageRDperformanceofsharksequenceusing PDC and 3D-HEVC algorithms under various configurations ........................................................ 92 Fig.4.14 AverageBDRATEresultsofthemodified3D-HEVC (using the PDC encoded I-frames) relative to the 3D-HEVC RefCTC and RefCTC_withoutContour configurations ........................................................ 94 Fig.5.1 Set of HEVC prediction modes replaced by the LLE-basedpredictionmodes,representedbydashed arrowsandboldnumbers ........................................... 100 Fig.5.2 SearchwindowusedbytheproposedLLE-basedintra prediction ............................................................ 101 Fig.5.3 Rate-distortionresultsforPlaneandToy(frame0) holoscopicimage .................................................... 102 Fig.5.4 Rate-distortionresultsforDemichelisCut(frame0) holoscopicimage .................................................... 102 Fig.5.5 Rate-distortionresultsforDemichelisSpark(frame0) holoscopicimage .................................................... 103 Fig.5.6 Rate-distortionresultsforLauraholoscopicimage ................ 103 Fig.5.7 Proposed training window and filter context for sparse-LSPalgorithm ............................................... 105 Fig.5.8 Selectionofnon-nullcoefficients’positionsusingTM algorithm(equivalenttok-NNmethod)withinacausal searchwindow ....................................................... 107 Fig.5.9 Rate-distortioncurvescomparingSLSP,LLE,TMand LSPmethodsusingHEVCstandard,forBarbaraimage .......... 113 Fig.5.10 Rate-distortioncurvescomparingSLSP,LLE,TMand LSPmethodsusingHEVCstandard,forWoolimage ............. 114 Fig.6.1 Samplepropagationusingafirst-orderlinearfilter contextforAngular10,18and26modes.(a)Angular 10—F1.(b)Angular18—F1.(c)Angular26—F1 ............... 119 H D V