Split repetitive image to find pattern

Hello

I have an image, which has been made by repeating the same (unknown) pattern. Usually there are 4 to 12 repetitions. This image is processed, as rotated, and cropped (taken a portion of it). A few examples of images (to be renamed as A for the code to run) are added here. My aim is to find this pattern, that is to split the image into complete equal tiles.

My code uses autocorrelation to find the repetition distance, but it seems it is not always working. It should find the right pattern, and also tell me if there are no complete tiles.

Rotation angle is fine. Code sometimes works, sometimes not. I can add more examples if needed.

If you have a better way to find the solution, please let me know

I hope it is clear what I ask

Thank you very much

%% autocorrelation
% ---------------------------------------------------------------------- %
[rows, cols] = size(A);

B = abs(fftshift(ifft2(fft2(A).*conj(fft2(A)))))./(rows*cols);
%B = medfilt2(B); 

%% threshold the matrix and find centroids
% ---------------------------------------------------------------------- %
C = B;
checkstart = max(C(:));
checkstart = round(checkstart,2);

for check = checkstart:-0.01:0
    for i = 1:rows
        for j = 1:cols
            if B(i,j)<=check
                C(i,j) = 0;
            else
                C(i,j) = 1;
            end
        end
    end

    L = bwlabel(C);
    s = regionprops(L,'centroid');

    if numel(s)>=3 && numel(s)<=10
        break    
    end
end

%% find distance and angle from the middle centroid
% ---------------------------------------------------------------------- %
midpoint = round(numel(s)/2);
middle = s(midpoint);

for p=1:numel(s)
    if p ~= midpoint   
        N = s(p);
        deltax = middle.Centroid(1)-N.Centroid(1);
        deltay = middle.Centroid(2)-N.Centroid(2);
        distance1(p) = sqrt((deltax.^2)+(deltay.^2));   
        distance(p) = round(distance1(p));         
        angle(p) = atand(deltay/deltax);
    end
end

mindistance = min(distance(distance>0));
for p=1:numel(distance)
    if distance(p) == mindistance
        minangle = angle(p);
     end
end

dif(1) = minangle-90;
dif(2) = minangle;
dif(3) = minangle+90;

adif = abs(dif);
adifmin = min(adif);

for q=1:numel(dif)
    if abs(dif(q))==adifmin
        anglechange = dif(q);
    end
end

if anglechange>=45
    anglechange = anglechange-90;
elseif anglechange<=-45
    anglechange = anglechange+90;
end

D = imrotate(A,anglechange);

%% create a grid
% ---------------------------------------------------------------------- %

[row, col] = size(D);

x = floor((col-1)/(mindistance));
y = floor((row-1)/(mindistance));

for xn=0:x
    xpos(xn+1) = 1+xn*(mindistance);
end

for yn=0:y
    ypos(yn+1) = 1+yn*(mindistance);
end

%% separate tiles
% ---------------------------------------------------------------------- %
w = 1;
for inc = 1:numel(xpos)-1
    for jnc = 1:numel(ypos)-1
        singletile{w} = D(ypos(jnc):ypos(jnc+1),xpos(inc):xpos(inc+1));
        w=w+1;
    end
end

Answer 1

[DGM]

This isn't really an answer so much. I was going to look into it, but I found that it was easier to rewrite it in order to figure out what it was doing. This is where it's at:

% autocorrelation
% ---------------------------------------------------------------------- %
B = abs(fftshift(ifft2(fft2(A).*conj(fft2(A)))))./numel(A);

imshow(imcomplement(B))

%%
% threshold the matrix and find centroids
% ---------------------------------------------------------------------- %
checkstart = max(B(:));
checkstart = round(checkstart,2);
for check = checkstart:-0.01:0
    C = B>check;
    CC = bwconncomp(C); % this should be faster
    if CC.NumObjects>=4 && CC.NumObjects<=10
        break    
    end
end
s = regionprops(CC,'centroid'); % do this outside

imshow(imcomplement(C))

%%
% find distance and angle from the middle centroid
% ---------------------------------------------------------------------- %

% find the actual geometrically-central blob
imcenter = fliplr(size(C,1:2))/2;
distfromcenter = sqrt(sum((vertcat(s.Centroid)-imcenter).^2,2));
[~,refidx] = min(distfromcenter); % the index of the reference peak

% find all other blobs
nonrefidx = 1:numel(s);
nonrefidx(refidx) = [];

% get distances and angles WRT the reference
delta = s(refidx).Centroid - vertcat(s(nonrefidx).Centroid);
distfromref = sqrt(sum(delta.^2,2))
anglefromref = atand(delta(:,2)./delta(:,1));

% minimize distance, get associated angle
[mindistance,idx] = min(distfromref);
minangle = anglefromref(idx);

% wrap the angle to (-45 45]
% this is the same as all the stuff with dif and the +-45 test
anglechange = 45 - mod(45 - minangle,90);

% rotate the image
D = imrotate(A,anglechange);

clc
mindistance
anglechange
imshow(imcomplement(D))

%%
% detile the image
% ---------------------------------------------------------------------- %

% get tiling
sz = size(D,1:2);
mindistance = round(mindistance);
tiling = floor(sz./mindistance); % [y x]

% use mat2cell()
M = mindistance*ones(tiling(1),1); % tile size vectors
N = mindistance*ones(tiling(2),1);
Dt = D(1:mindistance*tiling(1),1:mindistance*tiling(2)); % crop
tiles = mat2cell(Dt,M,N); % detile

% show the tiles
montage(tiles,'border',10,'backgroundcolor','m')

All of the supplied images are similar in that they do not have a full repetition of the pattern in at least one direction. While there does seem to be enough information to discern the correct spacing, the given method of finding the mindistance gives the wrong result for notile.mat and a.mat (these are duplicates), it seems to be off by a factor of sqrt(2) when it fails.

The ok.mat file seems to detile fine, though these patterns are obviously not exact replications.

I'd have to think about it more to see what can be done for notile.mat.

EDIT:

I replaced the first part with this:

% autocorrelation
% ---------------------------------------------------------------------- %
B = normxcorr2(A,A); % this seems to be more reliable
B = imtophat(B,ones(21)); % tophat filter
B = mat2gray(B); % normalize

... and it seems to work for notile.mat now. The detiling routine still doesn't do anything useful in that case, since there's only one full tile in the image, but it at least gets the right distance.

[Mat]

Thank you very much DGM, in the following days I am going to test this solution, which seems to fit my needs.

Answer 2

[Image Analyst]

Screenshots would help. Does your template (pattern you're searching the larger image for) change size or rotation when it's in the different locations? Have you tried normxcorr2 (demo attached)?

[Mat]

Sorry but this is not what I meant. I am not looking for a certain template. I don't know the template. The original image is made of repetition of the same template. Like in your example, imagine the photo is made of all identical squares of onions. Please plot the *.mat files I attached to see what my images look like, or the image below, where the tile to be found is called original tile, and it is COMPLETELY replicated 4 times in the image

or in this one where there are MANY more repetitions (more than 50, case extreme just to understand)

Answer 3

[Image Analyst]

If it's just a perfect replication of some tile, why can't you just scan across until a column or row is the same

[rows, columns] = size(m);
% First scan for a matching column
firstColumn= m(:, 1);
for col = 1 : columns
    if isequal(firstColumn, m(:, col))
        % This column is the same as the first so log it's size
        tileWidth = col - 1;
        break;
    end
end
% Next scan for a matching row
firstRow = m(1, :);
for row = 1 : rows
    if isequal(firstRow, m(row, :))
        % This row is the same as the first so log it's size
        tileHeight = row - 1;
        break;
    end
end

[DGM]

The patterns are not grid-aligned.

EDIT: ... and they aren't replicated exactly either.