Chaining array matches in Python
This seems like a fairly complicated task. Let me explain the scenario with small examples.
Consider 5 arrays a1, a2, a3, a4, and a5. These arrays are not important, I’m mentioning them for the sake of completeness. Consider 4 matches arrays m1, m2, m3, m4 of sizes 10, 9, 11 and 10. Each array basically tells you which element of the first array a<i> matched with second a<i+1>.
Eg. if m1 = [-1, 0, 2, -1, 3, 8, 7, -1, 9, 5] It means that the 0th element of a1 does not have a match, the 1st of a1 matches with the 0th element of a2 and the 2nd element of a1 matches with the 2nd element of a2.
Thus, the size of m1 = size of a1 and size of m2 = size of a2 etc.
Similarly, if m2 = [-1, 0, 2, 6, 3, 8, 7, -1, 9, 5] It establishes the correspondent matches between a2 and a3.
Here is my question. Is it possible to find out which element from a1 corresponds to elements in a3? My final goal is to establish this correspondence between a1 and a5.
For the a1 to a3, my matched new array will be m = [-1, -1, 2, -1, 6, 9, -1, -1, 5, 8] . To explain how I get this m array, for eg. m[4] = m2[m1[4]].
What is the most efficient way to do this?
A few notes:
- The
-1is merely an indicator to represent that there is no match and can be replaced with anything that would make the problem easier. - The biggest problem I face is that
m2[m1[7]]should ideally be-1sincem1[7]is-1, however, due to Python/numpy indexing rules,m2[-1]will be taken as the last element ofm2, which is not desirable in this case - This is just a toy example and my arrays and matches arrays will be of sizes ~2000 elements.
If anyone is interested in its application, or if extra information would help, this pertains to images feature matching. Using opencv I extract orb features and perform feature matches between three images I1, I2 and I3. I have correspondences between I1-I2 and I2-I3 and would like to compute the matches between I1-I3 indirectly using the above two correspondences.
One approach you could do is to entend each array m1, m2, …. by one value. Then replace that extra value and ‘-1’ by the (length-1) of next array m2, m3, … respectively.
But, in the last array, change ‘-1’ to ‘no match’ (or any other value you prefer), and append the same value.
m1 = [-1, 0, 2, -1, 3, 8, 7, -1, 9, 5] m2 = [-1, 0, 2, 6, 3, 8, 7, -1, 9, 5] m_list = [m1, m2] for i in range(len(m_list)-1): m_list[i] = [len(m_list[i+1]) if x==-1 else x for x in m_list[i]] m_list[i].append(len(m_list[i+1])) m_list[len(m_list)-1] = ['no match' if x==-1 else x for x in m_list[len(m_list)-1]] m_list[len(m_list)-1].append('no match') m1, m2 = m_list Now if you run m2[m1[7]], your output will be 'no match'.
Note : The m1, m2, …. you will get will have one extra length. So if you are using it somewhere else, be careful for any errors.
