I was thinking this problem seems like an anti-aliasing problem,
Am 13.09.2018 um 18:10 schrieb Rick C. Hodgin:
I was thinking this problem seems like an anti-aliasing problem,
It's not.
Aliasing is what happens when you reduce the _number_ of spatially structured values, rather than same number's scale or precision.
It's not even clear if your "three values" have any sort of spatial organization, which in the case at hand might simplify to ordering. Is this an ordered tuple, or just three numbers where nobody cares which of the three is labelled "v1", which v2 and which v3?
I have a situation where I have three values (v1, v2, v3) and they
have a max value each of 32, but more typically each will be 8 or less.
I need to scale up their values proportionally toward the next
largest multiple of 8 (if they don't already equal a multiple of 8).
For example:
v1 = 2
v2 = 3
v3 = 4
Here we have a total of 2+3+4 = 9, which would need to scale up to
16, being as it's the next multiple of 8.
I need the v1, v2, and v3 values to each scale up proportionally,
so that v3 gets the largest increase, v2 the second largest, and
v1 the smallest.
Mathematically I can determine how much they would scale with an
equation. But v1..v3 are integers, and they need to round to the
nearest integer values to be legitimate, which may require rounding
up in some cases, rounding down in others.
-----
I was thinking this problem seems like an anti-aliasing problem,
where perfect geometry is mapped into integer space, rounding up
to the next pixel, or down to the prior one.
I was wondering if anyone can think of an anti-aliasing algorithm
which would help in this case?
On 9/13/2018 7:07 PM, Hans-Bernhard Bröker wrote:
Am 13.09.2018 um 18:10 schrieb Rick C. Hodgin:
I was thinking this problem seems like an anti-aliasing problem,
It's not.
Aliasing is what happens when you reduce the _number_ of spatially
structured values, rather than same number's scale or precision.
You project a perfect representation of floating point geometry
onto an integer "matrix" and have to approximate coloring of the
fringe pixels based on how much of their area is covered, with
a blend of the color in use, its alpha channel if any, and the
background color you're overwriting.
But the point is, you take floating point values and project
them to integer boundaries. In the case of anti-aliasing, you
use that fractional portion to determine rounding up/down.
Am 14.09.2018 um 07:00 schrieb Rick C. Hodgin:
On 9/13/2018 7:07 PM, Hans-Bernhard Bröker wrote:
Am 13.09.2018 um 18:10 schrieb Rick C. Hodgin:
I was thinking this problem seems like an anti-aliasing problem,
It's not.
Aliasing is what happens when you reduce the _number_ of spatially
structured values, rather than same number's scale or precision.
You project a perfect representation of floating point geometry
onto an integer "matrix" and have to approximate coloring of the
fringe pixels based on how much of their area is covered, with
a blend of the color in use, its alpha channel if any, and the
background color you're overwriting.
I.e. exactly what I said: a reduction of the number of values, in this
case from infinitely many to a finite set.
But _nothing_ like that was even remotely hinted at in your actual
problem statement: no geometry, no floating-point data, nothing. Just
three integer numbers with no apparent relation to each other. So
there's no chance to get aliasing, and thus no way apply anti-aliasing.
But the point is, you take floating point values and project
them to integer boundaries. In the case of anti-aliasing, you
use that fractional portion to determine rounding up/down.
The difference is whether your input data is just a shapeless set of
numbers, or a function of the coordinates in some geometric space: a
"field" Aliasing is an artefact that happens when you sub-sample the geometric _coordinates_ of the field, quantization is what you reduce
the precision of the field's _values_.
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:
I have a situation where I have three values (v1, v2, v3) and they
have a max value each of 32, but more typically each will be 8 or less.
I need to scale up their values proportionally toward the next
largest multiple of 8 (if they don't already equal a multiple of 8).
For example:
v1 = 2
v2 = 3
v3 = 4
Here we have a total of 2+3+4 = 9, which would need to scale up to
16, being as it's the next multiple of 8.
I need the v1, v2, and v3 values to each scale up proportionally,
so that v3 gets the largest increase, v2 the second largest, and
v1 the smallest.
Mathematically I can determine how much they would scale with an
equation. But v1..v3 are integers, and they need to round to the
nearest integer values to be legitimate, which may require rounding
up in some cases, rounding down in others.
-----
I was thinking this problem seems like an anti-aliasing problem,
where perfect geometry is mapped into integer space, rounding up
to the next pixel, or down to the prior one.
I was wondering if anyone can think of an anti-aliasing algorithm
which would help in this case?
This problem isn't completely specified, because sometimes there is
more than one way to choose which to round up and which to round down.
The case you gave (v1,v2,v3) = (2,3,4) is pretty easy, but how would you
want to round (v1,v2,v3) = (5,8,11) ?
One way to handle this problem does have some resemblence to
antialiasing. You could use "error diffusion". In your case, you would compute (v1,v2,v3) = 16/9 * (2,3,4) = (3.55,5.33,7.11). (I am truncating
the decimals. They repeat, of course.) Then round v1 up to 4. The
error is -0.44. Add that to v2, computing v2 = 5.33-0.44 = 4.88. When
you round v2 up to 5, the error is -0.11. Then compute v3 = 7.11-0.11 =
7. The resulting triple is (v1,v2,v3) = (4,5,7).
I apologize for not explaining the problem well enough. I don't
know what you need to answer my question properly, and I'm not
sure I'm conveying it in a way you can receive properly to then
address it.
The problem (to me) is simple. I have three values (v1, v2, v3),
and they contain numbers.
The goal is to get v1+v2+v3 up to the
next even multiple of 8 boundary,
and to do so proportionally so
the biggest one gets the biggest increase, the next biggest the
next biggest increase, the smallest the smallest increase.
I was told by someone in comp.lang.c that this does have some
resemblance to a graphics algorithm. Scott writes:
"> As Anton mentioned, that does sound a lot like the
"> linear interpolation we use in graphics, or any quanti-
"> zation problem really."
Am 16.09.2018 um 13:36 schrieb Rick C. Hodgin:
I apologize for not explaining the problem well enough. I don't
know what you need to answer my question properly, and I'm not
sure I'm conveying it in a way you can receive properly to then
address it.
I think that for starters, you must stop jumping to conclusions. Or if
you do, you need to be more open for the idea that such jumps might land
you in the wrong place --- at least after having been told so.
The problem (to me) is simple. I have three values (v1, v2, v3),
and they contain numbers.
You just say "numbers", which begs the question: are these always
integer, too, or is that a requirement for your output only? I'll
assume integers throughout, for now.
The goal is to get v1+v2+v3 up to the
next even multiple of 8 boundary,
"Next" or "Next bigger"?
and to do so proportionally so
That doesn't mean what the following says:
the biggest one gets the biggest increase, the next biggest the
next biggest increase, the smallest the smallest increase.
That part cannot fully be satisfied, because there is not necessarily
"the" smallest or "the" next-biggest increase to assign. Think of cases where the sum of the inputs, was 7 (modulo 8), so you only get to add
one in total. Same goes for the inputs, too: how would you work on three identical numbers for input?
"Proportional" would not just mean sorting, but scaling the increments
like the inputs. I.e. all outputs would be the rounded result from multiplying each input by the target sum, then dividing it by the input
sum.
I was told by someone in comp.lang.c that this does have some
resemblance to a graphics algorithm. Scott writes:
"> As Anton mentioned, that does sound a lot like the
"> linear interpolation we use in graphics, or any quanti-
"> zation problem really."
I.e. even your source never claimed a relation to anti-aliasing, but
rather to quantization. Same as I did right away.
Am 16.09.2018 um 13:36 schrieb Rick C. Hodgin:
the biggest one gets the biggest increase, the next biggest the
next biggest increase, the smallest the smallest increase.
That part cannot fully be satisfied, because there is not necessarily "the" smallest or "the" next-biggest increase to assign. Think of cases where the sum of the inputs, was 7 (modulo 8), so you only get to add one in total. Same goes for the inputs, too: how would you work on three identical numbers for input?
"Proportional" would not just mean sorting, but scaling the increments like the inputs. I.e. all outputs would be the rounded result from multiplying each input by the target sum, then dividing it by the input sum.
I was told by someone in comp.lang.c that this does have some
resemblance to a graphics algorithm. Scott writes:
"> As Anton mentioned, that does sound a lot like the
"> linear interpolation we use in graphics, or any quanti-
"> zation problem really."
I.e. even your source never claimed a relation to anti-aliasing, but rather to quantization. Same as I did right away.
I don't see (2,3,4) as being easy. v1=2, v2=3, v3=4, total
of 9, rounding up to 16, means 7 can be added. How do you
distribute 7 amongst the 2,3,4 proportionally?
So long as the increase is proportional, it doesn't matter
too much which one receive the rounding up more.
One way to handle this problem does have some resemblence to
antialiasing. You could use "error diffusion". In your case, you would
compute (v1,v2,v3) = 16/9 * (2,3,4) = (3.55,5.33,7.11). (I am truncating
the decimals. They repeat, of course.) Then round v1 up to 4. The
error is -0.44. Add that to v2, computing v2 = 5.33-0.44 = 4.88. When
you round v2 up to 5, the error is -0.11. Then compute v3 = 7.11-0.11 =
7. The resulting triple is (v1,v2,v3) = (4,5,7).
This is what I would expect the values to be rounded up to.
I had not considered factoring in the previous error in the
next value. Are you applying it by size? Or just left-to-
right in this example?
Thank you for your assistance. And for reference, these
integers refer to how many bits are used to encode some-
thing. A value of 2 means 2^2, meaning there are 00, 01,
10, 11 values for that position. A value of 4 means there
are 2^4, with 0000..1111, meaning 15 values, etc. And
these values are being used for storage space in a compact
structure, and by increasing the bits, we allow for the
values of 00..11 (4 values) to be increased to 7 values
by increasing it from 2 to 3 (meaning 2 bits of storage
to 3 bits of storage).
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:
I don't see (2,3,4) as being easy. v1=2, v2=3, v3=4, total
of 9, rounding up to 16, means 7 can be added. How do you
distribute 7 amongst the 2,3,4 proportionally?
I view it as being easy, since rounding each of (3.55,5.33,7.11) to the nearest integer produces a sum of 16, which is what was desired.
On 9/18/2018 5:14 PM, Scott Hemphill wrote:
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:
I don't see (2,3,4) as being easy. v1=2, v2=3, v3=4, total
of 9, rounding up to 16, means 7 can be added. How do you
distribute 7 amongst the 2,3,4 proportionally?
I view it as being easy, since rounding each of (3.55,5.33,7.11) to the
nearest integer produces a sum of 16, which is what was desired.
Let's consider the possible range of values (we'll call them a,
b, and c instead of v1, v2, and v3).
If we consider a, b, c, all in the range from 1..32, we have a
4096 match exactly at the 8-bit boundary, and 28,672 need some
adjustment because their (a + b + c) % 8 does not equal 0.
If we apply projected increases and round, we find that of those
28,672 only 19,895 fall on an exact boundary using the project-
and-round logic, leaving 8,777 need post-project-and-round ad-
justment.
Here's the pseudo-code (written in Visual FoxPro, "ln" prefixes
mean "local numeric" and are just a convention):
lnMatch = 0 && Number that match exactly
lnMismatchType1 = 0 && Number that project exactly
lnMismatchType2 = 0 && Number that miss the projection
FOR lnA = 1 TO 32 && a = 1..32
FOR lnB = 1 TO 32 && b = 1..32
FOR lnC = 1 TO 32 && c = 1..32
* See where we are
lnABC = (lnA + lnB + lnC)
* Same as ((lnABC % 8) ? 0 : 8 - (lnABC % 8)) in C/C++:
lnTarget = lnABC + IIF(lnABC % 8 = 0, 0, 8 - (lnABC % 8))
lnDiff = lnTarget - lnABC
* Are we there?
IF lnDiff = 0
* Yes, it's on a boundary of 8
lnMatch = lnMatch + 1
ELSE
* Need to adjust up to next highest boundary of 8
lnAStep = lnA / lnABC
lnBStep = lnB / lnABC
lnCStep = lnC / lnABC
lnA2 = lnA + ROUND(lnDiff * lnAStep, 0) && Round to
lnB2 = lnB + ROUND(lnDiff * lnBStep, 0) && nearest
lnC2 = lnC + ROUND(lnDiff * lnCStep, 0) && whole number
* Compute our new total
lnABC2 = lnA2 + lnB2 + lnC2
lnDiff2 = lnTarget - lnABC2
IF lnDiff2 = 0
lnMismatchType1 = lnMismatchType1 + 1
ELSE
lnMismatchType2 = lnMismatchType2 + 1
ENDIF
ENDIF
NEXT
NEXT
NEXT
* Display the totals
? lnMatch, lnMismatchType1, lnMismatchType2
If I missed something, I'm open to correcting it.
That looks right. First, a side comment. You're making the arithmetic slightly more complicated than it needs to be. You don't have to
calculate the difference between the target and the total and the value
of the individual steps. You can simply calculate:
lnA2 = ROUND(lnA * lnTarget/lnABC),
etc.
"Rick C. Hodgin" <rick.c.hodgin@gmail.com> writes:
So there you have it. You will have to decide what to do with three fractions that all lie between 0 and one-half, or three fractions that
all lie between one-half and one.
For example, fA=0.3, fB=0.3, fC=0.4. Their total is one. Do you
promote fC to one because it's the biggest of the fractions? What if
lnA is a lot bigger than lnB or lnC? It might be that rounding fA to
one might be a smaller proportional error than rounding fC to one.
Similarly with, fA=0.6, fB=0.7, fC=0.7. Their total is two, but you
can't round them all up, because their total would then be three. So
which one do you demote: fA? Does it depend on the relative size of
lnA, lnB, and lnC? Here's another consideration: suppose lnB and lnC
have the same value. Do you want to preserve that equality even though
it might mean a greater relative error by demoting fA?
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 113 |
Nodes: | 8 (1 / 7) |
Uptime: | 114:45:06 |
Calls: | 2,501 |
Files: | 8,685 |
Messages: | 1,922,174 |