# US 2021/0243441 A1 · Method and apparatus for encoding/decoding video signal by using graph-based separable transform > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0243441 A1 - Document ID: US20210243441A1 - Status: Published application - Kind: A1 - Application number: 16/074,372 - Filed: 2017-02-01 - Published: 2021-08-05 - Earliest claimed: 2016-02-01 - Assignees: LG Electronics Inc.; University of Southern California - Applicants: LG Electronics Inc.; University of Southern California - Inventors: Hilmi E. EGILMEZ; Yung-Hsuan CHAO; Antonio ORTEGA; Bumshik LEE; Sehoon YEA - Web page: https://patentgrep.com/patent/US20210243441A1 ## CPC - H04N 19/12: Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264 - H04N 19/159: Prediction type, e.g. intra-frame, inter-frame or bidirectional frame prediction - H04N 19/176: the region being a block, e.g. a macroblock - H04N 19/61: in combination with predictive coding - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract The present invention provides a method for encoding a video signal on the basis of a graph-based separable transform (GBST), the method comprising the steps of: generating an incidence matrix representing a line graph; training a sample covariance matrix for rows and columns from the rows and columns of a residual signal; calculating a graph Laplacian matrix for rows and columns on the basis of the incidence matrix and the sample covariance matrix for rows and columns; and obtaining a GBST by performing eigen decomposition of the graph Laplacian matrix for rows and columns. ## Claims ### Claim 1 A method for encoding a video signal based on a graph-based separable transform (GBST), the method comprising: generating an incidence matrix corresponding to a line graph; training a sample covariance matrix for a row and a column from a row and a column of a residual signal; calculating a graph Laplacian matrix for a row and a column based on the incidence matrix and the sample covariance matrix for the row and the column; and obtaining the GBST by performing an eigen decomposition to the graph Laplacian matrix for the row and the column. ### Claim 2 (depends on 1) The method of claim 1, wherein the graph Laplacian matrix for the row and the column is defined by a link weighting parameter and a recursive loop parameter. ### Claim 3 (depends on 1) The method of claim 1, wherein two different Gaussian Markov Random fields (GMRFs) are used for modeling of an inter residual signal and an intra residual signal. ### Claim 4 (depends on 3) The method of claim 3, wherein, in the case of the intra residual signal, a one-dimensional GMRF comprises at least one of a distortion component of a reference sample, a Gaussian noise component of a current sample, or a spatial correlation coefficient. ### Claim 5 (depends on 3) The method of claim 3, wherein, in the case of the inter residual signal, a one-dimensional GMRF comprises at least one of a distortion component of a reference sample, a Gaussian noise component of a current sample, a temporal correlation coefficient, or a spatial correlation coefficient. ### Claim 6 A method for decoding a video signal based on a graph-based separable transform (GBST), the method comprising: extracting a residual signal from the video signal; performing an inverse-transform for the residual signal based on the GBST; and generating a reconstruction signal by adding the inverse-transformed residual signal to a prediction signal, wherein the GBST represents a transform generated based on line graphs, which are obtained by a Gaussian Markov Random Field (GMRF) modelling of a row and a column of the residual signal. ### Claim 7 (depends on 6) The method of claim 6, wherein the GBST is generated by the steps of: generating an incidence matrix corresponding to a line graph; training a sample covariance matrix for a row and a column from the row and the column of the residual signal; calculating a graph Laplacian matrix for a row and a column based on the incidence matrix and the sample covariance matrix for the row and the column; and obtaining a GBST by performing an eigen decomposition to the graph Laplacian matrix for the rows and the columns. ### Claim 8 An apparatus for encoding a video signal based on a graph-based separable transform (GBST), the apparatus comprising: a graph generation unit configured to generate an incidence matrix corresponding to a line graph; and a GBST unit configured to train a sample covariance matrix for a row and a column from a row and a column of a residual signal, calculate a graph Laplacian matrix for a row and a column based on the incidence matrix and the sample covariance matrix for the row and the column, and obtain the GBST by performing an eigen decomposition to the graph Laplacian matrix for the row and the column. ### Claim 9 (depends on 8) The apparatus of claim 8, wherein the graph Laplacian matrix for the row and the column is defined by a link weighting parameter and a recursive loop parameter. ### Claim 10 (depends on 8) The apparatus of claim 8, wherein two different Gaussian Markov Random Field (GMRFs) are used for modeling of an inter residual signal and an intra residual signal. ### Claim 11 (depends on 10) The apparatus of claim 10, wherein, in the case of the intra residual signal, a one-dimensional GMRF comprises at least one of a distortion component of a reference sample, a Gaussian noise component of a current sample, or a spatial correlation coefficient. ### Claim 12 (depends on 10) The apparatus of claim 10, wherein, in the case of the inter residual signal, a one-dimensional GMRF comprises at least one of a distortion component of a reference sample, a Gaussian noise component of a current sample, a temporal correlation coefficient, or a spatial correlation coefficient. ### Claim 13 An apparatus for decoding a video signal based on a graph-based separable transform (GBST), the apparatus comprising: a parsing unit configured to extract a residual signal from the video signal; an inverse transform unit configured to perform inverse transform on the residual signal based on the GBST; and a reconstruction unit configured to generate a reconstruction signal by adding the inverse-transformed residual signal and a prediction signal, wherein the GBST corresponds to a transform generated based on line graphs which are obtained by GMRF modeling of rows and columns of the residual signal. ### Claim 14 (depends on 12) The apparatus of claim 12, wherein the GBST is generated by the steps of: generating an incidence matrix corresponding to a line graph; training a sample covariance matrix for a row and a column from a row and a column of a residual signal; calculating a graph Laplacian matrix for a row and a column based on the incidence matrix and the sample covariance matrix for the row and the column; and obtaining a GBST by performing an eigen decomposition to the graph Laplacian matrix for the row and the column.