[go: up one dir, main page]

WO2018143687A1 - Procédé et appareil permettant d'effectuer une transformation à l'aide d'une transformée de rangée-colonne - Google Patents

Procédé et appareil permettant d'effectuer une transformation à l'aide d'une transformée de rangée-colonne Download PDF

Info

Publication number
WO2018143687A1
WO2018143687A1 PCT/KR2018/001378 KR2018001378W WO2018143687A1 WO 2018143687 A1 WO2018143687 A1 WO 2018143687A1 KR 2018001378 W KR2018001378 W KR 2018001378W WO 2018143687 A1 WO2018143687 A1 WO 2018143687A1
Authority
WO
WIPO (PCT)
Prior art keywords
transform
inverse
row
column
matrix
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/KR2018/001378
Other languages
English (en)
Korean (ko)
Inventor
구문모
귈레우즈오누르
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
LG Electronics Inc
Original Assignee
LG Electronics Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by LG Electronics Inc filed Critical LG Electronics Inc
Publication of WO2018143687A1 publication Critical patent/WO2018143687A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
    • H04N19/124—Quantisation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
    • H04N19/13—Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/44—Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding

Definitions

  • the present invention relates to a method and apparatus for encoding / decoding a video signal, and more particularly to a row-column having better characteristics or orthogonality or separabiity to a given target transform.
  • a technique for designing a transform (row-column transform, hereinafter referred to as 'RCT').
  • Compression coding refers to a series of signal processing techniques for transmitting digitized information through a communication line or for storing in a form suitable for a storage medium.
  • Media such as an image, an image, an audio, and the like may be a target of compression encoding.
  • a technique of performing compression encoding on an image is called video image compression.
  • Next-generation video content will be characterized by high spatial resolution, high frame rate and high dimensionality of scene representation. Processing such content would result in a tremendous increase in terms of memory storage, memory access rate, and processing power.
  • the present invention proposes a method of improving coding efficiency through a new transform design.
  • the present invention seeks to design a transform that provides a low complexity and reasonable coding gain.
  • the present invention intends to design a row-column transform (RCT) that approximates a target transform well.
  • RCT row-column transform
  • An object of the present invention is to provide a method of designing a row-column transform (RCT) having characteristics of orthogonality or separability.
  • RCT row-column transform
  • the present invention proposes an encoder / decoder structure to reflect a new transform design.
  • the present invention provides a method for improving coding efficiency through a new transform design.
  • the present invention provides a method for designing a row-column transfum (RCT) that can approximate more important transform basis vectors by applying weights to transform basis vectors.
  • the present invention provides a method of designing all row-column transforms (RCTs) to have orthogonality, respectively.
  • the present invention provides a method of approximating by multiplying a permutation matrix before a target transform in order to increase an approximation of a row-column transform (RCT).
  • RCT row-column transform
  • the present invention provides a method of designing a separable row-column transform (RCT) having only one transform in a row direction and one in a column direction.
  • RCT separable row-column transform
  • the present invention provides a method of applying an absolute value operator when applying a Hungarian method to find a substitution matrix.
  • the present invention can design a much more efficient row-column transformation in terms of encoding efficiency and complexity when applying transform to encode and transmit still images or moving images. As such, the coding efficiency can be improved through the new transform design.
  • FIG. 1 is a schematic block diagram of an encoder in which encoding of a video signal is performed as an embodiment to which the present invention is applied.
  • FIG. 2 is a schematic block diagram of a decoder in which decoding of a video signal is performed according to an embodiment to which the present invention is applied.
  • FIG. 3 is a diagram illustrating a division structure of a coding unit according to an embodiment to which the present invention is applied. It is a figure for demonstrating.
  • FIG. 4 is an embodiment to which the present invention is applied and shows a schematic block diagram of an RCT unit to which an RCT is applied.
  • FIG. 5 is an embodiment to which the present invention is applied and is a diagram for explaining a process of applying ROT.
  • FIG. 6 is a diagram for describing a process of applying an RCT in which two substitution matrices (P, Q) are used as an embodiment to which the present invention is applied.
  • FIG. 7 and 8 illustrate schematic block diagrams of an RCT unit for determining an RCT using two substitution matrices (P, Q) and an inverse RCT unit corresponding thereto according to embodiments to which the present invention is applied.
  • FIG. 9 is an embodiment to which the present invention is applied and is a flowchart illustrating a process of obtaining RCT coefficients.
  • FIG. 10 is a flowchart illustrating a process of performing decoding based on RCT coefficients according to an embodiment to which the present invention is applied.
  • the present invention relates to a row transform set based on a given transformation matrix (H) and an error tolerance parameter in a method for performing a transformation using a row-column transform.
  • H transformation matrix
  • RCT Row-Column Transform
  • the first and second substitution matrices are derived through an optimization process, and the optimization process is determined based on matching between a row-column transform (RCT) matrix and the given transform matrix (H), A row-column transform matrix is derived using the row transform set and the column transform set.
  • RCT row-column transform
  • H given transform matrix
  • the present invention is characterized in that the weight is applied in the process of inducing RCT.
  • the RCT matrix may be weighted to transform basis vectors.
  • the type Garlician method is applied, and the type Garlician method is performed by using an input to which the absolute value operator is applied.
  • each of the transforms in the row transform set and the column transform set is orthogonal.
  • each of the row transform set and the column transform set is a separable transform having a single transform.
  • the present invention utilizes a row-column transform to perform an inverse transform.
  • CLAIMS 1.
  • a method comprising: receiving a video signal; Obtaining coefficients from the video signal through entropy decoding and dequantization; Performing inverse-permutation and inverse-transform on the coefficients; And reconstructing the video signal using an inverse transformed coefficient, wherein the inverse transformed coefficient is applied by a first inverse transform matrix, an inverse-column transform set, an inverse-row transform set, and a second inverse transform matrix in order. It provides a method characterized in that it is obtained by.
  • performing the inverse transform comprises: applying a first inverse substitution matrix to the coefficients; Performing an inverse-column transform on coefficients to which the first inverse substitution matrix is applied; Performing an inverse-row transform on the inverse-column transformed coefficients; And applying a second inverse substitution matrix to the inverse-row transformed coefficients.
  • the inverse transform matrix is characterized by being weighted to transform basis vectors.
  • each transform in the inverse-row transform set and the inverse-column transform set is characterized by being orthogonal.
  • each of the inverse-row transform set and the inverse-column transform set is a separable transform having a single transform.
  • the present invention utilizes a row-column transform to perform the transformation.
  • a row transform set, a column transform set, and first and second substitution matrices are based on a given transformation matrix H and an error tolerance parameter.
  • a quantization unit configured to perform quantization on the quantized RCT coefficients, and an entropy encoding unit performing entropy encoding on the quantized RCT coefficients, wherein the RCT coefficients include the first substitution matrix, the row transform set, the column transform set, and the second transform coefficient.
  • An apparatus is provided which is obtained by applying a substitution matrix in order.
  • the present invention provides an apparatus for performing inverse transformation using a row-column transform, comprising: a receiver configured to receive a video signal; An entropy decoding unit for entropy decoding the residual signal; An inverse quantizer for inversely quantizing the entropy decoded residual signal to obtain a coefficient; An inverse transform unit performing inverse-permutation and inverse transform on the coefficients; And a reconstruction unit for reconstructing the video signal by using an inverse transform coefficient, wherein the inverse transform coefficient is applied by a first inverse transform matrix, an inverse-column transform set, an inverse-row transform set, and a second inverse transform matrix in order. It provides an apparatus characterized in that it is obtained by.
  • FIG. 1 is a schematic block diagram of an encoder in which encoding of a video signal is performed as an embodiment to which the present invention is applied.
  • the encoder 100 includes an image segmentation unit 110, the conversion unit (1 20), a quantization unit 130, an inverse quantization unit 140, an inversion unit 150, a filtering unit (ISO) , Decryption It may include a decoded picture buffer (DPB) 170, an inter predictor 180, an intra predictor 185, and an entropy encoder 190.
  • the image divider 110 may divide an input image (or a picture or a frame) input to the encoder 100 into one or more processing units.
  • the processing unit encoding a tree unit may be: (Transform Unit ⁇ ) (CTU : Coding Tree Unit), coding units (CU:: Coding Unit), prediction unit (PU Prediction Unit) or a conversion unit.
  • the terms are only used for the convenience of description of the present invention, the present invention is not limited to the definition of the terms.
  • the term coding unit is used as a unit used in encoding or decoding a video signal, but the present invention is not limited thereto and may be appropriately interpreted according to the present invention.
  • the encoder 100 may generate a residual signal by subtracting a prediction signal output from the inter predictor 180 or the intra predictor 185 from the input image signal, and generate the residual signal. Is transmitted to the conversion unit 120>.
  • the transform unit 120 may generate a transform coefficient by applying a transform technique to the residual signal.
  • the conversion process may be applied to pixel blocks having the same size as the square, or may be applied to blocks of variable size rather than square.
  • the conversion technique described in the present invention may be applied to pixel blocks having the same size as the square, or may be applied to blocks of variable size rather than square.
  • RCT Row-Column Transform
  • the RCT unit may be included in or replaced with the conversion unit.
  • the transform unit may use various transform techniques, and one of them may use RCT.
  • the present invention provides a method for improving coding efficiency through a new transform design.
  • the present invention provides a method of designing a Row-Column Transform (RCT) that can approximate more important transform basis vectors by applying weights to transform basis vectors.
  • RCT Row-Column Transform
  • the present invention provides a method of designing all row-column transforms (RCTs) to have orthogonality.
  • the present invention also provides a method of approximating by multiplying a permutation matrix before a target transform in order to increase the approximation of a row-column transform (RCT).
  • RCT row-column transform
  • the present invention provides a method of designing a separable row-column transform (RCT) having only one transform in a row direction and one in a column direction.
  • RCT separable row-column transform
  • the present invention provides a method of applying an absolute value operator when applying a Hungarian method to find a substitution matrix.
  • the quantization unit 130 quantizes the transform coefficients to the entropy encoding unit 190.
  • the entropy encoding unit 190 may entropy-code the quantized signal and output the quantized signal in a bitstream.
  • the quantized signal output from the quantization unit 130 may be used to generate a prediction signal.
  • the quantized signal may recover the residual signal by applying inverse quantization and inverse transformation through inverse quantization unit 140 and inverse transform unit 150 in a loop.
  • the reconstructed signal may be generated by adding the reconstructed residual signal to a prediction signal output from the inter predictor 180 or the intra predictor 185.
  • deterioration of the block boundary may occur due to the quantization error generated in the above compression process. This phenomenon is called blocking artifacts, which is one of the important factors in evaluating image quality.
  • a filtering process may be performed. Through this filtering process, the image quality can be improved by removing the blocking degradation and reducing the error of the current picture.
  • the filtering unit 160 applies filtering to the reconstruction signal and outputs it to the reproduction apparatus or transmits the decoded picture buffer to the decoded picture buffer 170.
  • the filtered signal transmitted to the decoded picture buffer 170 may be used as the reference picture in the inter predictor 180. As such, by using the filtered picture as a reference picture in the inter prediction mode, not only image quality but also encoding efficiency may be improved.
  • the decoded picture buffer 170 references the filtered picture in the inter prediction unit 180. You can save it for use as a picture.
  • the inter prediction unit 180 performs temporal prediction and / or spatial prediction to remove temporal redundancy and / or spatial redundancy with reference to a reconstructed picture.
  • the reference picture used to perform the prediction is a transformed signal that has been quantized and dequantized in units of blocks at the time of encoding / decoding, a blocking artifact or a ringing artifact may exist. have.
  • the inter prediction unit 180 may interpolate the signals between pixels in sub-pixel units by applying a lowpass filter in order to solve the performance degradation caused by the block continuity or quantization.
  • the subpixel refers to a virtual pixel generated by applying an interpolation filter
  • the integer pixel refers to an actual pixel existing in the reconstructed picture.
  • the interpolation method linear interpolation, bi-linear interpolation, and Wiener filter may be applied.
  • the interpolation filter may be applied to a reconstructed picture to improve the precision of prediction.
  • the inter prediction unit 180 generates an interpolation pixel by applying an interpolation filter to integer pixels, and uses an interpolated block composed of interpolated pixels as a prediction block. Predictions can be performed.
  • the intra predictor 185 may predict the current block by referring to sample poles around the block to which current encoding is to be performed.
  • the intra The prediction unit 185 may perform the following process to perform intra prediction. First, reference samples necessary for generating a prediction signal may be prepared. The prediction signal may be generated using the prepared reference sample. Then, the prediction mode is encoded. In this case, the reference sample may be prepared through reference sample padding and / or reference sample filtering. Since the reference sample has been predicted and reconstructed, there may be a quantization error. Accordingly, the reference sample filtering process may be performed for each prediction mode used for intra prediction to reduce such an error.
  • a prediction signal generated through the inter predictor 180 or the intra predictor 185 may be used to generate a reconstruction signal or to generate a residual signal.
  • 2 is a schematic block diagram of a decoder in which decoding of a video signal is performed as an embodiment to which the present invention is applied.
  • the decoder 200 includes a parser (not shown), an entropy decoder 210, an inverse quantizer 220, an inverse transformer 230, a filter 240, and a decoded picture buffer (DPB). It may include a decoded picture buffer unit) 250, an inter predictor 260, and an intra predictor 265.
  • the reconstructed video signal output through the decoder 200 may be reproduced through the reproducing apparatus.
  • the decoder 200 may receive a signal output from the encoder 100 of FIG. 1, and the received signal may be entropy decoded through the entropy decoding unit 210. have.
  • the inverse quantization unit 220 obtains a transform coefficient from the entropy decoded signal using the quantization stem size information.
  • the inverse transform unit 230 inversely transforms the transform coefficient to obtain a residual signal.
  • the present invention provides a method of designing a new RCT transform, and the embodiments described herein may be applied. In addition, the processes of the embodiments described in the encoder may be reversely applied.
  • a reconstructed signal is generated by adding the obtained residual signal to a prediction signal output from the inter predictor 260 or the intra predictor 265.
  • the filtering unit 240 applies filtering to the reconstructed signal and outputs the filtering to the reproducing apparatus or transmits it to the decoded picture buffer unit 250.
  • the filtered signal transmitted to the decoded picture buffer unit 250 may be used as the reference picture in the inter predictor 260.
  • FIG. 3 is a diagram for describing a division structure of a coding unit according to an embodiment to which the present invention is applied.
  • the encoder converts one image (or picture) into a rectangular coding tree unit (CTU). Coding Tree Unit) can be divided into units. Then, one CTU is sequentially encoded according to a raster scan order. For example, the size of the CTU may be set to any one of 64x64, 32x32, and 16x16, but the present invention is not limited thereto.
  • the encoder may select and use the size of the CTU according to the resolution of the input video or the characteristics of the input video.
  • the CTU may include a coding tree block (CTB) for luma components and a coding tree block (CTB) for two chroma components.
  • One CTU may be decomposed into a quadtree (QT) structure.
  • QT quadtree
  • one CTU may be divided into four units having a square shape and each side is reduced by half in length.
  • the decomposition of this QT structure can be done recursively.
  • the root node of the QT may be associated with a CTU.
  • the QT may be split until it reaches a leaf node, where the leaf node may be referred to as a coding unit (CU).
  • CU coding unit
  • a CU may mean a basic unit of coding in which an input image is processed, for example, intra / inter prediction is performed.
  • the CU may include a coding block (CB) for luma components and a CB for two chroma components.
  • the size of the CU may be determined by any one of 64 ⁇ 6 4 , 32 ⁇ 32, 16 ⁇ 16, and 8 ⁇ 8.
  • the present invention is not limited thereto, and in the case of a high resolution image, the size of the CU may be larger or more diverse.
  • a CTU corresponds to a root node and has a smallest depth (ie, level 0) value.
  • the CTU may not be divided according to the characteristics of the input image. In this case, the CTU corresponds to a CU.
  • the CTU may be decomposed in QT form, and as a result, lower nodes having a depth of level 1 may be generated. And, a node that is no longer partitioned (ie, a leaf node) in a lower node having a depth of level 1 corresponds to a CU.
  • CU a
  • CU a
  • CU b
  • CU j
  • FIG. 3 (b) CU (a), CU (b), and CU (j), which perform on nodes a, b, and j, are divided once in the CTU and have a depth of level 1.
  • At least one of the nodes having a depth of level 1 may be split into QT again.
  • a node that is no longer partitioned (ie, a leaf node) in a lower node having a depth of level 2 corresponds to a CU.
  • CU (C), CU (h), CU (i) which complies with nodes c, h and i, are divided twice in the CTU and have a depth of level 2.
  • At least one of the nodes having a depth of 2 may be divided into QTs.
  • a node that is no longer partitioned (ie, a leaf node) in a lower node having a depth of level 3 corresponds to a CU.
  • CU (d), CU (e), CU (f), and CU (g) for nodes d, e, f, and g are divided three times in the CTU, and level 3 Has a depth of
  • the maximum size or the minimum size of the CU may be determined according to characteristics (eg, resolution) of the video image or in consideration of encoding efficiency. In addition, information on this or information capable of deriving the information may be included in the bitstream. Can be.
  • a CU having a maximum size may be referred to as a largest coding unit (LCU), and a CU having a minimum size may be referred to as a smallest coding unit (SCU).
  • LCU largest coding unit
  • SCU smallest coding unit
  • a CU having a tree structure may be hierarchically divided with predetermined maximum depth information (or maximum level information).
  • Each partitioned CU may have depth information. Since the depth information indicates the number and / or degree of division of the CU, the depth information may include information about the size of the CU.
  • the size of the SCU can be obtained by using the size and maximum depth information of the LCU. Or conversely, using the size of the SCU and the maximum depth information of the tree, the size of the LCU can be obtained.
  • information indicating whether the corresponding CU is split may be delivered to the decoder.
  • the information may be defined as a split pull lag, and may be represented by a syntax element "split_cu_f lag".
  • the division flag may be included in all CUs except the SCU. For example, if the split flag value is '1', the CU is divided into 4 CUs again, and if the split flag value is 0, the CU is no longer divided and the coding process for the CU is not divided. Can be performed.
  • the division process of the OJ has been described as an example, but the QT structure described above may also be applied to the division process of a transform unit (TU), which is a basic unit for performing transformation.
  • TU transform unit
  • a TU may be hierarchically divided into QT structures from a CU to be coded.
  • a CU may correspond to a root node of a tree for a transform unit (TU).
  • the TU divided from the CU may be divided into smaller lower TUs.
  • the size of the TU may be determined by any one of 32x32, 16x16, 8x8, and 4x4.
  • the present invention is not limited thereto, and in the case of a high resolution image, the size of the TU may be larger or more diverse.
  • information indicating whether the corresponding TU is divided may be delivered to the decoder.
  • the information may be defined as a split transform flag and may be represented by a syntax element "split_transform_flag".
  • the division conversion flag may be included in all TUs except the TU of the minimum size. For example, when the value of the division conversion flag is '1', the corresponding TU is divided into four TUs again. When the value of the division conversion flag is '0', the corresponding TU is no longer divided.
  • a CU is a basic unit of coding in which intra prediction or inter prediction is performed. It can be divided into: (Prediction Unit PU) units of the input picture predicting unit CU in order to more efficiently coded.
  • (Prediction Unit PU) units of the input picture predicting unit CU in order to more efficiently coded.
  • the PU is a basic unit for generating a prediction block, and may generate different prediction blocks in PU units within one CU.
  • the PU may be divided differently according to whether an intra prediction mode or an inter prediction mode is used as a coding mode of a CU to which the PU belongs.
  • 4 is an embodiment to which the present invention is applied and shows a schematic block diagram of an RCT unit to which an RCT is applied.
  • the present invention provides an RCT in which transformations that are not two-dimensional separable are defined based on sets of one-dimensional linear transformations and basis ordering permutation.
  • the invention provides RCT by optimizing the set of one-dimensional .linear transforms applied to the rows and columns of blocks, given non-separable block transforms for the region of interest in the image, and obtaining alignment substitution for the optimal transform coefficients.
  • Equation (1) the first basis vector (b a vector si s) of the j-th row conversion, it can be expressed by the following matrix shown in Equation (1).
  • Equation 2 an RCT matrix, G (N 2 xN 2 ), may be defined as Equation 2 below.
  • the transformation of the block X can be obtained by applying a substitution matrix after obtaining G T x.
  • Row-Column Transform (RCT) Design The optimal row-column (RC) approximation of the desired transform matrix H 3 ⁇ 4 ( ⁇ ''; ⁇ ' ) can be expressed as an optimization problem in .
  • Equation 4 is due to a P permutation matrix constraint, "is a joint optimization statement.
  • a row-column (RC) constraint for G can be explicitly written as follows. , Where J is the j th column of C ' '' . At this time, B 3 ⁇ 4 C (3 "'is the same as Equation 5 .
  • Equation 8 If you replace Mr. 'in Equation 5 Equation 6 can be derived.
  • ⁇ is the (i, j> th NXN partition of the matrix H and ⁇ can be expressed as Equation (8).
  • the RCT unit 400 to which the present invention is applied may largely include an RCT inducing unit 410 and an RCT applying unit 420.
  • the RCT derivation unit 410 generates a row transform set, a column transform set, and a permutation matrix based on a given transformation matrix ⁇ and an error tolerance parameter. ) Can be induced.
  • the substitution matrix may be derived through an optimization process.
  • the optimization process may be determined by matching a Low-C and n Transform (RCT) matrix with the given transform matrix (H).
  • RCT matrix may be derived using the row transform set and the column transform set.
  • the row-column transform matrix may mean the matrix G of Equations 2 and 3 above.
  • the RCT applying unit 420 may obtain a transform coefficient based on the row transform set and the column transform set.
  • the transformation coefficient may be obtained by performing a column transformation after performing a row transformation.
  • the RCT applying unit 420 may obtain a row-column transform (RCT) coefficient by applying the substitution matrix to the transform coefficient.
  • RCT row-column transform
  • the operation of the RCT unit 400 is divided into the RCT inducing unit 410 and the RCT applying unit 420, but the present invention is not limited thereto, and the process of obtaining the RCT coefficient is It can be understood that the conversion unit 120 is performed.
  • the RCT unit 400 may be included in, or replaced with, the conversion unit.
  • the transform unit may use various transformation techniques, and one of them may use RCT.
  • FIG. 5 is a diagram for describing a process in which an RCT and a substitution matrix are applied as an embodiment to which the present invention is applied.
  • the present invention uses a Row-Column Transform (RCT) as a new method for approximating non-separable transforms.
  • RCT Row-Column Transform
  • the RCT may be defined as a set of one-dimensional transforms applied to the rows and columns of the signal blocks followed by substitution of coefficients.
  • the RCT proposed as an embodiment of the present invention is more of a non-separable transform It is advantageous in that it can maintain the complexity of separable transforms while providing good approximations.
  • RCT requires 2N 3 (or multiply-adds of 21 ⁇ 2 109 ⁇ in case fast conversion is used, while general non-separable conversion). (non-separable transform) has the computational complexity of.
  • FIG. 6 is a diagram illustrating a process of designing an RCT in which two substitution matrices (P, Q) are used as an embodiment to which the present invention is applied.
  • the present invention provides various embodiments for designing a Row-Column Transform (RCT) in a new way to better approximate a target transform.
  • RCT Row-Column Transform
  • Weighted Row-Column Transform (RCT) Design Algorithm An embodiment of the present invention provides a method of designing a weighted RCT (hereinafter, referred to as a weighted RCT 'or a weighted RCT'). .
  • Equation 9 may be used to find the weighted RCT.
  • Equation 9 minimize "'H” PG) -d "ia ⁇ ⁇ P T w J '
  • G represents an RCT matrix
  • P represents a substitution matrix
  • weight w is defined by the following equation (10).
  • Equations 9 and 10 may be applied to the RCT design algorithms Al, A2, and A3 described herein.
  • Forward transform (forward transform) and inverse transformation (inverse transform) with respect to the embodiments 2 uses both of the substitution matrix Q and p are the same as PG Q ⁇ f Q T T T GP respectively.
  • P and Q may be applied to all embodiments, but in the embodiments 1,2 and 4, Q may be regarded as a case of identity matrix I.
  • G may consist of a row, converting the (s row transform) and the heat conversion (column transform). For example, ⁇ is equal to multiplying 1 ( ⁇ " for each row (i-th row) and then multiplying C (j) 1 ⁇ for each column (j-th column), where G is each It is equivalent to multiplying C (j) for the column (column j) and then multiplying R "> for each row (column i).
  • Example 4 which will be described below, since a separable row-column transform (RCT) is presented, all R ( “are the same as R and It may mean that all c (j> are equal to c.
  • RCT row-column transform
  • the first substitution matrix Q is applied to block X, and After performing the row transformation and the column transformation, a series of processes for obtaining the transformation coefficient Y can be confirmed by applying the second substitution matrix P.
  • the RCT unit 700 to which the present invention is applied may be divided into a first substitution matrix application unit 710, a row transformation application unit 720, a column transformation application unit 730, and a second substitution matrix application unit. 740 may include.
  • the first substitution matrix applying unit 710 may apply a first substitution matrix Q to the pixel data X.
  • the RCT unit 700 may first perform row transformation and column transformation.
  • the row transformation may be performed by the row transformation application unit 720
  • the column transformation may be performed by the column transformation application unit 730.
  • the second substitution matrix applying unit 740 applies the second substitution matrix P by Transformation coefficient Y can be obtained.
  • the inverse RCT unit 800 to which the present invention is applied may be divided into a first inverse substitution matrix application unit 810, an inverse-row transformation application unit 820, an inverse-column transformation application unit 830, and the like.
  • a second inverse substitution matrix application 840 .
  • the inverse RCT unit 800 obtains the pixel data X by applying an inverse transform to a transform coefficient.
  • the first inverse-substitution matrix applying unit 810 may apply a first inverse-substitution matrix ( ⁇ ⁇ ) to the transform coefficient (k).
  • the inverse RCT unit 800 may first perform inverse-column conversion and then perform inverse-row transformation.
  • the inverse-column transformation may be performed by the inverse-% conversion application unit 820, and the inverse-row transformation may be performed by the inverse-row transformation application unit 830.
  • the second inverse substitution matrix applying unit 840 may obtain the transform coefficient ⁇ by applying the second substitution matrix.
  • the present embodiment it is assumed that both ⁇ and Q are applied and that R ′′) and c ( j ) may be differently applied to each row and column, but the present invention is not limited thereto.
  • the configuration of FIGS. 6 to 8 may be applied to each embodiment.
  • X and Y have a 2D block data type, but the present invention is not limited thereto, and a lexicographical order (eg The conversion matrix can be applied after converting to 1D vector according to, row-first or column-first.
  • the block data to which the substitution matrix is applied may be converted back into a 2D block data type in order to apply a row direction or a column direction transformation.
  • the order may be according to the dictionary order.
  • the present invention provides a method for determining a column transform C (i) when the row transform R (i) and the substitution matrix P are fixed.
  • L k ⁇ A ⁇ is the k th basis vector of the i th row transformation and l JX l is the first basis vector of the j th row transformation.
  • ⁇ is a matrix of H divided by the same size and has the dimension of XN.
  • diag (P T w) diag (P T z) may be used.
  • diag (x) represents a function that finds the NxN diagonal matrix by placing the Nxl input vector x on the diagonal line of the NxN matrix and setting the remaining elements to zero.
  • equations (12) to (14) can be used to determine the column transform (C ) .
  • Equation 14 C (i) represents a column transform, which can be calculated by multiplying two orthogonal matrices by V '. And the above V c ⁇ f 'in two orthogonal matrices can be derived by applying Singular Value Decomposition (SVD) to Equation (13).
  • the present invention provides a column transform C (i) and substitution. When the matrix (P) is fixed, it provides a way to determine the row transform 13 ⁇ 4.
  • Equation 18 The matrix H in Equation 16 is equal to H in Equation 11.
  • 11 represents a row transform, which can be calculated by multiplying two orthogonal matrices by,. And in the two orthogonal matrices,
  • the invention relates to a method of designing an orthogonal RCT.
  • the algorithm Al represents a flow to which the scheme described in Equations 11 to 18 is applied.
  • step 1 the encoder is k k0, G (0), P (0) I, R U) — CC ( ⁇ C ;, for all /, c— ⁇ ) may be initialized, wherein steps 4 to 7 correspond to Equations 11 to 14, which are row transforms. ) The process of determining the column transform C (i) when R (i) and the substitution matrix (P) are fixed.
  • Steps 8 to 11 are based on Equations 15 to IS, and include column transform C (i) and a substitution matrix.
  • (P) is fixed, the row A process of determining a row transform R ′′ ) is shown.
  • the column transforms C (i) obtained from the above steps 4 to 7 are input to the above steps 8 to 11, and the row transforms obtained from the current while-loop iteration R (i) column transforms transform) C (i) can be used in the next while-loop iteration.
  • the while-loop is repeated until the amount of change in the error value obtained in step 15 becomes small enough to converge.
  • the weight is also reflected (for example, diag (P T w) or diag (P T Z )), and when the change amount (c) of the difference is hardly changed.
  • the substitution matrix P is obtained in step 13
  • G and ⁇ W T are input to a Hungarian method algorithm, which can be confirmed by Equation 19 below.
  • P (k) represents a P matrix value in the k-th iteration
  • G (k) can be interpreted in the same manner.
  • Equation 21 an optimal substitution matrix P may be obtained by Equation 21 below, and an optimal substitution matrix Q may be obtained by Equation 22 below. Equation 21
  • Tr ( ') denotes a trace (trace)
  • p represents the substitution matrix
  • Equation 22 can be solved by finding an optimal assignment between H and G column vectors, and the type Garian method can be applied. Through this, an optimal substitution matrix Q can be obtained.
  • the present invention provides an overall algorithm for a new substitution method for RCT design, as shown in Table 2 below.
  • Algorithm A2 represents an exemplary flow for the method of Equations 20-22. For example, steps 11 to 12 first find P (k), and then Q (k) is determined as the new P (k). Steps 11 to 12 may be performed in reverse. For example, first Q (k) is determined and then Q (k) can be used to determine P (k).
  • the substitution matrix Q of Equation 20 may be used for the RCT design in the algorithms ⁇ 1, A2, and A3.
  • Algorithm A2 solves Equations 20 and 22 to find transform matrix G 'and substitution matrix P', Q * (step 16).
  • the encoder transforms a given A row transform set, a column transform set and a permutation matrix can be derived based on the matrix H and the error tolerance parameter.
  • the substitution matrix may mean a matrix obtained by replacing a row of an identity matrix.
  • the encoder can perform initialization such as k — 0, G (0) — I, P (0) — I, Q (0) —] :, c — ⁇ (step 1). If C> ⁇ , k ⁇ / f N ( ⁇ ⁇ ' ' ⁇ ' ⁇ ⁇ ⁇ ' ) can be obtained (steps 3 to 6). In this case, singular value decomposition with respect to Equation (16)
  • the encoder may acquire or derive G ij ⁇ ⁇ ⁇ ⁇ ⁇ using Equation 18 (step 7).
  • ⁇ ( ⁇ ) ⁇ ⁇ instead of G can be described by the following equation (23).
  • P (k) and Q (k) mean P and Q substitution matrices in the k-th while-loop iteration, and P (k) obtained in step 11 may be used to obtain Q in step 12. Can be.
  • step 14 the amount of difference between QHP and G is calculated. If the amount of change of the difference is small enough, the while-loop is terminated.
  • the present invention provides a method of designing a separable RCT with only unique transformations for row and column directions.
  • the separable RCT may mean that a single transform exists in the row and column directions, respectively.
  • the method of determining one row direction transformation is represented by Equation 24 below.
  • the present invention proposes the following two methods for determining one row direction transformation.
  • Equation 2 5 is a transformation commonly used in the row direction The formula for finding the j th column. Ie 2
  • the present invention proposes the following two methods for determining one thermal direction conversion.
  • Equation 28 is an i-th column vector of the forward transform c T applied to all columns.
  • Equation 26 Denotes the j-th block diagonal matrix divided by the same size in ⁇ as shown in Equation 26, and has an NxN dimension.
  • r is the j th column of the transformation matrix R commonly used in the row direction r
  • step 5 When deriving R (C) in step 4 (step 5), it is assumed that C (R) is given and fixed. Steps 4 and 5 may be switched.
  • matrices such as unit matrix, discrete cosine transform (DCT), karhunen—loeve transform (KLT), and sparse orthonormal transform (SOT), such as R, ml , and C ma may be starting points.
  • DCT discrete cosine transform
  • KLT karhunen—loeve transform
  • SOT sparse orthonormal transform
  • step 9 the difference between HP and G is calculated, and if there is little change, the algorithm is considered to have converged and the while-loop Will end.
  • Example 5 A method of using an absolute value operator when applying a Hungarian method to find a substitution matrix
  • the present invention proposes a method of applying an absolute operator when applying a Hungarian method to find a substitution matrix.
  • the input J of the Hungarian method can be understood and defined in the following equation (30).
  • the present invention is not limited thereto, and the input J may be modified according to the Hungarian algorithm.
  • the present invention proposes a method of using J calculated by the following equation (31) as an input to a type Garian algorithm.
  • ⁇ Denotes an absolute value operator for each element. If the G r H matrix is input directly to the Hungarian algorithm (where the cost matrix can be-G T H o ⁇ ), the elements of the matrix are negative. It may have a sign. If there is an element with a large absolute value and a negative sign in the G T H matrix, the absolute value of the dot product is excluded except that the corresponding base vector pairs (the base vector of G and the base vector of H) are in opposite directions. Although the matching is good because the value is large, the phenomenon may be excluded from the matching by considering the corresponding cost value large.
  • Equation 32 the problem of finding an optimal allocation may be summarized as in Equation 32 below.
  • the encoder may derive the row transform set, the column transform set, and the first and second substitution matrices based on the given transformation matrix) and the error tolerance parameter (S910).
  • the first and second substitution matrices are derived through an optimization process, and the optimization process is performed by using a low-column transform (RCT) matrix with the given transform matrix (H). It can be determined based on the match.
  • RCT low-column transform
  • the row-column transform matrix may be derived using the row transform set and the column transform set, wherein the RCT matrix is weighted to transform basis vectors. It features.
  • the type Garlician method is applied, the type Garlician method may be performed by using an input to which the absolute value operator is applied.
  • each of the transforms in the row transform set and the column transform set is orthogonal.
  • each of the row transform set and the column transform set is a separable transform having a single transform.
  • the encoder may obtain a Row-Column Transform (RCT) coefficient based on the row transform set, the column transform set, and the first and second substitution matrices (S920).
  • RCT Row-Column Transform
  • the first substitution matrix, the row transformation set, the column transformation set, and the nearly b substitution matrix may be sequentially applied.
  • the encoder may perform quantization and entropy encoding on the RCT coefficients (S930).
  • 10 is a flowchart illustrating a process of performing decoding based on RCT coefficients according to an embodiment to which the present invention is applied.
  • the decoder to which the present invention is applied may receive a video signal.
  • the decoder may obtain transform coefficients from the video signal through entropy decoding and inverse quantization.
  • the transform coefficient may refer to a Row-Column Transform (RCT) coefficient to which the present invention is applied, and the RCT coefficient may mean that the embodiments described herein are applied.
  • RCT Row-Column Transform
  • the decoder comprises: a first station for the substitution matrix transform coefficients - can be applied to (1 st inverse permutation matrix) ( S1010).
  • the decoder may perform an inverse-column transform on coefficients to which the first inverse substitution matrix is applied (S1020).
  • the decoder may perform an inverse-row transform on the inverse-column transformed coefficient (S1030).
  • the decoder it is possible to apply the second reverse substitution matrix (2 nd inverse- permutation matrix) for an inverse transform coefficients (S1040).
  • the inverse transform matrix used in the inverse transform process may be weighted to transform basis vectors.
  • each transform in the inverse-row transform set and the inverse-column transform set is all orthogonal.
  • each of the inverse-row transform set and the inverse-column transform set is a separable transform having a single transform.
  • the decoder may reconstruct the video signal using the pixel data (S1050).
  • the embodiments described herein may be implemented and performed on a processor, microprocessor, controller, or chip.
  • the functional units illustrated in FIGS. 1, 2, 4, and 7 to 8 may be implemented by a computer, a processor, a microprocessor, a controller, or a chip.
  • the decoder and encoder to which the present invention is applied include a multimedia broadcasting transmitting and receiving device, a mobile communication terminal, a home cinema video device, a digital cinema video device, a surveillance camera, a video chat device, a real time communication device such as video communication, a mobile streaming device, Storage media, camcorders, video on demand (VoD) service providing devices, internet streaming service providing devices, three-dimensional (3D) video devices, video telephony video devices, and medical video devices, and the like, for processing video signals and data signals Can be used for.
  • a multimedia broadcasting transmitting and receiving device include a mobile communication terminal, a home cinema video device, a digital cinema video device, a surveillance camera, a video chat device, a real time communication device such as video communication, a mobile streaming device, Storage media, camcorders, video on demand (VoD) service providing devices, internet streaming service providing devices, three-dimensional (3D) video devices, video telephony video devices, and medical video devices, and the like, for processing video signals and
  • the processing method to which the present invention is applied can be produced in the form of a program executed by a computer, and can be stored in a computer-readable recording medium.
  • Multimedia data having a data structure according to the present invention can also be stored in a computer-readable recording medium.
  • the computer readable recording medium includes all kinds of storage devices for storing computer readable data.
  • the computer-readable recording medium may include, for example, a Blu-ray disc (BD), a universal serial bus (USB), a ROM, a RAM, a CD-ROM, a magnetic tape, a floppy disk, and an optical data storage device.
  • the Computer-readable recording media include media embodied in the form of carrier waves (eg, transmission over the Internet).
  • the bit stream generated by the encoding method may be stored in a computer-readable recording medium or transmitted through a wired or wireless communication network.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)

Abstract

La présente invention concerne un procédé permettant d'effectuer une transformation à l'aide d'une transformée de rangée-colonne, le procédé comprenant les étapes consistant à : dériver un ensemble de transformées de rangées, un ensemble de transformées de colonnes, et des première et seconde matrices de permutation sur la base d'une matrice de transformation donnée (H) et d'un paramètre de tolérance d'erreur donné; acquérir des coefficients de transformée de rangée-colonne (RCT) sur la base de l'ensemble de transformées de rangées, de l'ensemble de transformées de colonnes et des première et seconde matrices de permutation; et effectuer une quantification et un codage entropique sur les coefficients RCT, les coefficients RCT étant acquis par l'application, dans cet ordre, de la première matrice de permutation, de l'ensemble de transformées de rangées, de l'ensemble de transformées de colonnes et de la seconde matrice de permutation..
PCT/KR2018/001378 2017-02-01 2018-02-01 Procédé et appareil permettant d'effectuer une transformation à l'aide d'une transformée de rangée-colonne Ceased WO2018143687A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US201762453477P 2017-02-01 2017-02-01
US62/453,477 2017-02-01

Publications (1)

Publication Number Publication Date
WO2018143687A1 true WO2018143687A1 (fr) 2018-08-09

Family

ID=63039943

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/KR2018/001378 Ceased WO2018143687A1 (fr) 2017-02-01 2018-02-01 Procédé et appareil permettant d'effectuer une transformation à l'aide d'une transformée de rangée-colonne

Country Status (1)

Country Link
WO (1) WO2018143687A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110224828A (zh) * 2019-07-17 2019-09-10 江苏南工科技集团有限公司 一种基于量子技术的加密算法

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20080020947A (ko) * 2006-08-25 2008-03-06 엔비디아 코포레이션 전력 소비를 감소시키면서 데이터 값 배열에 대해 2-차원변환을 수행하기 위한 방법 및 시스템
KR20120098500A (ko) * 2011-02-25 2012-09-05 삼성전자주식회사 영상의 변환 및 역변환 방법, 및 이를 이용한 영상의 부호화 및 복호화 장치
KR20140119822A (ko) * 2011-10-18 2014-10-10 주식회사 케이티 영상 부호화 방법, 영상 복호화 방법, 영상 부호화기 및 영상 복호화기
WO2014200322A2 (fr) * 2013-06-14 2014-12-18 삼성전자 주식회사 Procédé et dispositif de conversion de signal
KR20150090206A (ko) * 2013-01-30 2015-08-05 인텔 코포레이션 차세대 비디오를 위한 코딩을 위한 콘텐츠 적응적 파라메트릭 변환

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20080020947A (ko) * 2006-08-25 2008-03-06 엔비디아 코포레이션 전력 소비를 감소시키면서 데이터 값 배열에 대해 2-차원변환을 수행하기 위한 방법 및 시스템
KR20120098500A (ko) * 2011-02-25 2012-09-05 삼성전자주식회사 영상의 변환 및 역변환 방법, 및 이를 이용한 영상의 부호화 및 복호화 장치
KR20140119822A (ko) * 2011-10-18 2014-10-10 주식회사 케이티 영상 부호화 방법, 영상 복호화 방법, 영상 부호화기 및 영상 복호화기
KR20150090206A (ko) * 2013-01-30 2015-08-05 인텔 코포레이션 차세대 비디오를 위한 코딩을 위한 콘텐츠 적응적 파라메트릭 변환
WO2014200322A2 (fr) * 2013-06-14 2014-12-18 삼성전자 주식회사 Procédé et dispositif de conversion de signal

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110224828A (zh) * 2019-07-17 2019-09-10 江苏南工科技集团有限公司 一种基于量子技术的加密算法
WO2021008561A1 (fr) * 2019-07-17 2021-01-21 江苏南工科技集团有限公司 Algorithme de chiffrement utilisant une technologie quantique
CN110224828B (zh) * 2019-07-17 2023-06-20 江苏南工科技集团有限公司 一种基于量子技术的加密算法

Similar Documents

Publication Publication Date Title
US11973963B2 (en) Transform-based image coding method and device
US11265549B2 (en) Method for image coding using convolution neural network and apparatus thereof
KR102385399B1 (ko) 비디오 압축을 위한 변환을 구성하는 방법 및 장치
KR101901355B1 (ko) 최적화 함수를 이용하여 그래프 기반 예측을 수행하는 방법 및 장치
CN107431813B (zh) 使用基于图的变换处理视频信号的方法和装置
US12368855B2 (en) Transform-based image coding method and apparatus therefor
EP4294012B1 (fr) Procédé de codage vidéo sur la base d'une transformée secondaire et dispositif associé
US10567763B2 (en) Method and device for processing a video signal by using an adaptive separable graph-based transform
EP3334163A1 (fr) Dispositif et procédé pour effectuer une transformation à l'aide d'une mise à jour de coefficient de singleton
US10743025B2 (en) Method and apparatus for performing transformation using layered givens transform
US12088804B2 (en) Method and device for encoding/decoding video signal by using optimized conversion based on multiple graph-based model
US11470316B2 (en) Method and device for performing transformation by using layered-givens transform
US20210329249A1 (en) Image coding method based on secondary transform and apparatus therefor
KR101912769B1 (ko) 그래프 템플릿으로부터 유도된 변환을 이용하여 비디오 신호를 디코딩/인코딩하는 방법 및 장치
US11368691B2 (en) Method and device for designing low-complexity calculation DST7
WO2017057922A1 (fr) Procédé et dispositif pour le codage/décodage de signal vidéo au moyen de transformée d'élévation en ondelettes à base de graphe
KR20180089858A (ko) 레이어드 기븐스 변환을 이용하여 변환을 수행하는 방법 및 장치
KR20170074948A (ko) 일반화된 그래프 파라미터를 이용하여 그래프 기반 변환을 수행하는 방법 및 장치
US11503292B2 (en) Method and apparatus for encoding/decoding video signal by using graph-based separable transform
WO2018143687A1 (fr) Procédé et appareil permettant d'effectuer une transformation à l'aide d'une transformée de rangée-colonne
WO2017057923A1 (fr) Procédé d'encodage/décodage de signal vidéo au moyen d'un graphe unique optimisé
US20210195241A1 (en) Method and device for performing transform using row-column transforms

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 18748089

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 18748089

Country of ref document: EP

Kind code of ref document: A1