How to find combination of linear transformations to recover original Matrix with wrap?

Specific Domains
1

Given

obj::CircularArray{Bool,2,BitMatrix}

that has undergone a combination of linear transformations

  • circshift(A::AbstractMatrix, shifts::NTuple{2,<:Integer})
  • rotl90(A::AbstractMatrix, k::Integer)
  • reverse(A::AbstractMatrix; dims::Integer)
  • permutedims(m::AbstractMatrix)

how can I recover the inverse of linear transformations?

For example,

a = [3, 4, 21, 22, 25, 26, 28, 29, 30, 45, 46, 47, 49, 53, 54, 71, 72, 75, 78, 97, 101, 102, 123, 124, 125, 126, 149, 150, 175, 550, 551, 574, 575, 576, 577, 598, 599, 600, 603, 622]
b = [11, 17, 37, 38, 39, 40, 41, 63, 64, 65, 89, 464, 488, 489, 490, 512, 513, 514, 515, 516, 536, 542, 560, 561, 564, 567, 568, 584, 585, 586, 588, 590, 592, 593, 594, 610, 611, 614, 617, 618]
A = reshape((1:25^2) .∈ Ref(a), 25, 25)
B = reshape((1:25^2) .∈ Ref(b), 25, 25)

Here is A
Screen Shot 2020-10-11 at 6.59.45 PM
and B
Screen Shot 2020-10-11 at 7.00.07 PM

Through inspecting the images I was able to find that A can be obtained from B through

findall(A) == findall(circshift(B, (11, 3)))

However, I am still missing the mathematical foundation to implement the following:

function magic(A::AbstractMatrix{<:Boo},
               B::AbstractMatrix{<:Boo})
    # Finds R βˆ‹ B * R == A
end

trans = qd_rigid(A, B, (25, 25), 3Ο€/2)[1]

Gives the AffineMap I can use to recover the image! :slight_smile:

2

RegisterQD.jl was the right solution!

1 Like
3

Ended up filling an issue since it seems there are some issues with using qd_rigid directly.

4

Keep in mind that RegisterQD is not set up to test reflections (unless you provide an initial guess that has a reflection in it) or periodic boundary conditions. You might be able to pass in a custom array type that implements whatever boundary conditions you want, though; the key requirement is on the behavior of warp from ImageTransformations.

5

Based on that feedback,

"""
    find_affine(A::CircularArray, B::CircularArray)
"""
function find_affine(A::CircularArray, B::CircularArray)
    size(A) == size(B) || throw(ArgumentError("A and B have different dimensions"))
    for (rev, rot, pd, r, c) in product(0:2, 0:1:3, false:true, 0:size(A, 1), 0:size(A, 2))
        x = rev == 0 ? B : reverse(B, dims = rev)
        x = rotl90(x, rot)
        x = pd ? permutedims(x) : x
        circshift(x, (r, c)) == A && return (rev, rot, pd, r, c)
    end
    throw(ErrorException("No match!"))
end

Maybe brute forcing it isn’t too bad. The search space is 16,224. Going to test that and then from that I can construct the affine map (Transformation) for it.