An algorithm to find the closest match between 2 arrays of RGB pixel tuples

Question

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.

Answer 1

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).

Answer 2

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]$.