Efficient/Fastest pattern matching on integer vector

Question

Haider Ali 2022-6-19

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1743540-efficient-fastest-pattern-matching-on-integer-vector

评论： Image Analyst 2022-6-20

Hello,

Problem Staement:

Given a uint16 data vector vec in format [ID1 ID2 data ID1 ID2 data ...] and ID pairs mat pattern, find data associated with each ID pair and fill the 3rd column of output vector out with first 2 columns containing ID pairs.

Assumption:

It is assumed that the data in vec has both noise and missing because of which an ID pair is searched ([0 6]) and then the previous ([0 4]) and next ([0 8]) ID pairs are also searched to reliably get the data value of each ID pair.

Goal:

Find the most time efficient method to fill the output vector out.

Methods:

A simple nested loop based method which first searches for an ID pair in data vector vec and then matches its previous and next ID pairs for confirmation and get the associated data. The code is given below which takes roughly 2300 sec on my computer.

load vec;
load pattern;
load out;
len = length(out);
no_of_IDs_to_search = 1000;
tic
for j = 2:no_of_IDs_to_search % skip searching for ID pairs at 1st location
    ind = strfind(vec,pattern(j*2-1:j*2)); % firstly, find all indices of a single ID pair e.g. [0 2] or [0 6]
    ind(ind<4 | ind>((len-1)*3)) = []; % remove indices to aviod errors
    if (~isempty(ind))
        for k = 1:length(ind) % search through all indices and determine if previous and next IDs are a match
            if (isequal(vec(ind(k)-3:ind(k)-3+1), pattern((j-1)*2-1:(j-1)*2)) && isequal(vec(ind(k)+3:ind(k)+3+1), pattern((j+1)*2-1:(j+1)*2)))
                out(j,3) = vec(ind(k)+2); %update the corresponding index in output vector
                break; % break if previous, current and next IDs are a match
            end
        end
    end
end
toc

2. Some algorithm based on regular expressions, specifically Lookaround Assertions?

3. Maybe some C/C++ based mex implementation?

Thank you.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Image Analyst 2022-6-19

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1743540-efficient-fastest-pattern-matching-on-integer-vector#answer_988825

normxcorr2_demo.m

You could also try normalized cross correlation. A 2-d demo is atached that finds a template inside a larger image.

2 个评论
显示无隐藏无

Haider Ali 2022-6-20

@Image Analyst Are you suggesting looping over 3 ID pairs [previousID1 previousID2 NaN currentID1 currentID2 NaN nextID1 nextID2 NaN] at a time and finding normalized correlation for each of them?

Image Analyst 2022-6-20

No, I'm not. Honestly your scanning and using isequal() at each window location should be fine. I was just thinking that normxcorr2 might be a little faster since it's normalized but I was thinking to use it on the 1-D vector. Most Image Processing Toolbox functions can also be used on 1-D vectors as well as 2-D images.

请先登录，再进行评论。