1
$\begingroup$

So I'm looking for a bit of an abstract algorithm and I'd appreciate any references to read up on. This is a bit tough to explain but I'll try my best.

Suppose we have 2 arrays of RGB pixel tuples-

A -> {(56, 39, 75), (125, 222, 32), (156, 201, 102)}

B -> {(125, 195, 93), (53, 31, 67), (118, 219, 48)}

I'd like the sort the second array in such a way that for each index of the 2 arrays, the corresponding RGB tuple pairs have the least deviation in value such that the optical difference between the 2 tuples is imperceptible to the human eye. For example, the difference between (122, 36, 18) and (126, 31, 25) is imperceptible, this is what we want.

For the example arrays A and B, I think sorting B like so will keep the arrays as optically identical as possible- {(53, 31, 67), (118, 219, 48), (125, 195, 93)}

Constraints

  • Both arrays are of same length
  • The RGB pixel tuples themselves must remain unchanged, only their order in the array should be changed.
  • The first array must remain unchanged, only the second should be sorted accordingly
  • There may not be enough optimal elements in the second array to provide a perfect/good match, in this case the least amount of sacrifices will be preferred. The end goal is for the new pixel array to be as identical to the original array as possible. The least amount of sacrifices will ensure that the arrays of pixels, when turned into a picture, will look as identical as possible. Note: By the word "sacrifice", I mean when the deviation in 2 pixel tuples is enough for the human eye to notice a difference.
$\endgroup$
  • $\begingroup$ What is meant by "least deviation in value"? What is the precise definition of "deviation"? How do you compute the overall deviation, given the difference of each pair of elements? Please specify the problem carefully by giving a precise and general description of the desired solution, and how to verify whether a proposed solution is indeed correct. $\endgroup$ – D.W. Feb 2 at 18:06
  • $\begingroup$ @D.W. deviation just means |value1 - value2|. I edited my question to add some explaination $\endgroup$ – Chase Feb 3 at 5:09
  • $\begingroup$ This still doesn't specify what solutions are valid. There might be no way to get all elements simultaneously each achieving their lowest possible deviation. So, what do you want to do then? That will involve some kind of tradeoff, which needs to be made precise in some way -- and only you can specify it. I don't see any clear, general specification of what is the correct or allowable answer. A single example is not a substitute for a general specification. $\endgroup$ – D.W. Feb 3 at 5:18
  • $\begingroup$ @D.W. sorry, this is really hard to explain in a general case, so I changed the entire question to my specific case. It's for steganography basically. So I need the modified array to be as close to the original as possible, in a sense that the human eye wouldn't be able to tell the difference. $\endgroup$ – Chase Feb 3 at 8:39
  • $\begingroup$ I notice that you changed the question in a way that invalidates the existing answer. We normally prefer that you don't do that, and instead ask a new question. Maybe it doesn't matter much in this case as this is such a narrow question. As far as the modified question, I still don't see a clear problem specification. We'd need a precise specification of how to measure "optical difference" between two arrays. It's not enough to tell us how to measure the deviation between two tuples; we need to know how to assess an entire array. $\endgroup$ – D.W. Feb 4 at 1:01
0
$\begingroup$

You can't satisfy both goals. Suppose $A=[10,20,30]$ and $B=[10,20,30]$; then you presumably want the modified $B$ to be $[10,20,30]$. Now suppose $A=[10,20,30]$ and $B=[10,30,20]$; then you presumably want the modified $B$ to be $[10,20,30]$. The original A and the modified B are the same in both cases, so there is no way to tell from them what the original $B$ was (both remain a possibility).

$\endgroup$
  • $\begingroup$ Dammit, this is what I was scared of, the possibility of such an algorithm to even exist. Is there any way at all to achieve this task? $\endgroup$ – Chase Feb 3 at 18:14
  • $\begingroup$ @Chase, I think I've already answered that -- there is no way to achieve this, not with these requirements. $\endgroup$ – D.W. Feb 3 at 18:20
  • $\begingroup$ wellp, I changed the question again for it to have only 1 goal. The optically identical one. I'd appreciate an answer to that. $\endgroup$ – Chase Feb 3 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.