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
  • 1
    $\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
  • 1
    $\begingroup$ An example is not a substitute for a definition or specification. Also, you can only optimize one objective function. It's not possible to simultaneously minimize the deviation/difference and also minimize the number of elements that don't get their optimal match, since now it's unclear how to trade off between those two when it's impossible to simultaneously optimize both. This site is not made for repeated discussion or interaction or many rounds to try to extract a clear problem specification, so what you're asking might not fit our format well. $\endgroup$ – D.W. Feb 4 at 1:02
1
$\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).

| cite | improve this answer | |
$\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
1
$\begingroup$

The question in its current form has a simple answer: This is an instance of the Assignment Problem, or equivalently of finding a minimum-weight matching in a bipartite graph.

  1. Decide on a cost function $f(x, y)$ to measure the dissimilarity between two given RGB tuples $x$ and $y$ -- that is, this function should assign identical RGB tuples a cost of zero, and the more dissimilar two RGB tuples are, the higher the cost they should be assigned. (E.g.: Euclidean distance, or maximum absolute difference of the 3 components.)
  2. Construct a complete bipartite graph with a vertex in part A for each element in array A, a vertex in part B for each element in array B, and an edge of weight $f(A[i], B[j])$ between the $i$-th vertex in part A and the $j$-th vertex in part B.
  3. Use one of the algorithms for solving the Assignment Problem (these include the Hungarian algorithm, which will take $O(n^3)$ time in this case, and linear programming) to find an optimal matching (subset of edges such that each vertex is incident on at most one edge).
  4. Loop through the vertices in part A: For the $i$-th A-vertex, read off the vertex it is matched with in part B to determine what element to put in $B[i]$.
| cite | improve this answer | |
$\endgroup$

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.