Opened 5 years ago
Closed 4 years ago
#687 closed defect (fixed)
P1034 - Wrap around in scaling list coding
Reported by: | bheng | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | |
Component: | spec | Version: | VVC D7 vE |
Keywords: | Cc: | ksuehring, bbross, XiangLi, fbossen, jvet@… |
Description
For scaling list coding, there seems to be a wraparound process missing for the nextCoef derivation.
Specifically, the nextCoef is an accumulation of delta values, which could be as small as -128 each time:
nextCoef += scaling_list_delta_coef[ id ][ i ]
There is no wrapping process here, so after accumulating a few coefficients, nextCoef could be a very large negative number.
ScalingList[id][i] is just set equal to nextCoef.
ScalingList[ id ][ i ] = nextCoef
The value of ScalingList[id][i] is added to the predicted value and modulo wrapped:
ScalingMatrixRec[ id ][ x ][ y ] = ( ScalingMatrixPred[ x ][ y ] + ScalingList[ id ][ k ] + 256 ) % 256 ) (7-72)
The wrapping used here assumes that the (ScalingMatrixPred + ScalingList) sum is no smaller than -256. However, as shown above, ScalingList could be a very large negative value. That would require a modulo of a negative number, which is undefined in the spec.
For example, the sequence of coefficients [144, 16, 144, 16, 144, 16, ... ] in scan order, requires all scaling_list_delta_coef = -128. It's impossible to code this sequence without either creating a negative modulo situation above, or coding delta values outside the legal range [-128,127] (like VTM does).
Assuming it was not intended to make certain patterns of scaling lists impossible to encode, I believe the nextCoeff value should be wrapped to stay within [-128,127].
Also, there seems to be a left parenthesis missing in equation (7-72) above.
Change history (10)
comment:1 Changed 5 years ago by delagrangep
comment:2 Changed 5 years ago by bbross
- Resolution set to fixed
- Status changed from new to closed
Thanks for reporting.
This will be fixed JVET-P2001-vD.
comment:3 Changed 5 years ago by bheng
Thanks for confirming the problem.
Is it clear in the text that the result of that "& 255" with a negative value will be unsigned (0-255) and not signed (-128 to 127)? Or would there need to be something additional in the text to implement the "cast to uint8" process?
comment:4 Changed 5 years ago by ochubach
Hello Brian, all.
Thank you for catching this point. Because the "&" operation is not defined for negative numbers, I am not sure whether there is sense in adding it into the spec, since it's not going to solve the problem and may confuse other experts who will be reading it. We had modulo operation for defining nextCoef in our old version of the spec, but then removed it, since, as it was mentioned, it is an intermediate value and we thought it can be an implementation issue whether to allow wrap around or not. How about putting modulo back: ScalingList[ id ][ i ] = (nextCoef +256)%256. Would that solve the problem? This would not require defining of undefined "&" for negative numbers
comment:5 Changed 5 years ago by bbross
- Resolution fixed deleted
- Status changed from closed to reopened
I'll re-open this ticket until we have a working solution.
comment:6 Changed 5 years ago by bbross
- Version changed from VVC D7 vC to VVC D7 vE
comment:7 Changed 5 years ago by delagrangep
From the spec:
& | Bit-wise "and". When operating on integer arguments, operates on a two's complement representation of the integer value. When operating on a binary argument that contains fewer bits than another argument, the shorter argument is extended by adding more significant bits equal to 0. |
This means that it is defined for negative numbers, using two's complement representation (negative number 'val' represented as 2^{n} + val, with n as big as needed, or n = representation bit depth)
My understanding is that this also means that the result is unsigned (otherwise we would need to define when the result is signed).
See for example:
- Ref position for DMVR (8-438)
- Bitstream conformance of mv for IBC (8.6.2.1)
In thoses examples, one operand is signed but the result is obviously unsigned.
Note: I think the result of >> and << keep the sign of first operand ('arithmetic' shift), but and/or/xor result is always unsigned. Well, actually I think thoses bit-wise operators result in a binary representation, and exact signed/unsigned integer interpretation is clarified by the context.
Thus, the bitwise operators may need some clarification, but the same definitions and same kind of examples are found in HEVC... and we survived. So maybe it is just fine as-is.
I then suggest either
- change (7-71) et (7-72) with & 255 as above
- or change (7-72) as follows:
ScalingMatrixRec[ id ][ x ][ y ] = ( ScalingMatrixPred[ x ][ y ] + ScalingList[ id ][ k ] + 8192 ) % 256
comment:8 Changed 5 years ago by bheng
Thank you delagrangep for clarifying. I agree with your reasoning. The output of the & operation must already be understood to be an unsigned integer, otherwise it would be broken in several other places (like computing fractional MV components).
The "& 255" solution is cleaner in my opinion. I'd suggest we go with that as was originally suggested, so we can get the problem fixed and close this ticket. I notice in draft vE it's been changed to "& 256" so it's somewhere in-between at the moment.
Will you provide a similar fix for the software as well (using & rather than %)?
comment:9 Changed 5 years ago by bheng
I believe the software has been fixed with merge request jvet/VVCSoftware_VTM!1169.
As of Q0041-v1, the text still needs to change from "& 256" to "& 255" in equations (106) and (107) of Section 7.4.3.18.
comment:10 Changed 4 years ago by bbross
- Resolution set to fixed
- Status changed from reopened to closed
Thanks, the remaining issue is fixed in JVET-Q2001-v3.
Good catch, I did not have in mind that % was not defined for negative numbers.
I suggest changing (7-72) to:
ScalingMatrixRec[ id ][ x ][ y ] = ( ScalingMatrixPred[ x ][ y ] + ScalingList[ id ][ k ] ) & 255
and, for editorial consistency reason, change (7-71) to:
ScalingMatrixDCRec[ id − 14 ] = ( ScalingMatrixDCPred + scaling_list_dc_coef[ id − 14 ] ) & 255
Rationale: we just want 8-bit overflow, and cast the result to uint8.
Such operation in syntax (for nextCoef) would be redundant: it is implementation-specific whether numbers are allowed to grow, or overflow as either int8 or uint8.