1

I'm a beginner in matlab programming and i'm having some troubles with template matching. I have a few white boxes with a black border (link for pic below) along with some text and I want to extract all the boxes,and there's also one that has an X in it(it's a multiple choice answer). In the beginning I used normxcorr2 , but the problem is that due to the many white pixels of the template, I get allot of irrelevant templates like only white spaces. I was looking for an algorithm that does template matching only on 0's , so I could get templates that have black squares only. I hope I made myself clear, thanks :)

http://i91.photobucket.com/albums/k284/Chris2401/sqrTemplate.png

rayryeng
  • 102,964
  • 22
  • 184
  • 193
Chris Post
  • 117
  • 1
  • 13

1 Answers1

2

EDIT: May 2nd, 2014

Now understanding what you are trying to achieve, I can now help you solve your problem. As you are a beginner to MATLAB, I will use a more simpler approach (even though there are more sophisticated methods to help you figure this out) as I want to demonstrate how the algorithm works.

You basically want to implement normxcorr2, but you only want to include pixels that are marked as black in the template. You also want to skip locations in the search image that are not black. In that case, I will layout the algorithm for you step by step, then write some code.

  1. Read in the template and extract those pixel locations that are black
  2. In a sliding window fashion, for each image patch of the same size as the template that is in the search image...
    1. If the entire image patch is white, skip
    2. Extract the same locations that are black
    3. Compute the NCC using those locations only.
  3. The output will be a map that contains the NCC for each location in the search image

I will not handle the case of the border pixels in the search image, as I am assuming that you want to be able to match something in the search image with the full size of the template.

Here are some assumptions. Let's assume the following variables:

  • imTemplate - The template image, such as the one that you have showed me
  • imSearch - The image we wish to search for when doing this NCC stuff

I am also assuming that each of the images are binary, as the title of your post has "0 or 1" in it.

As such, I have the following code for you:

[rowsSearch colsSearch] = size(imSearch); % Get dimensions of search image
[rowsTemp colsTemp] = size(imTemplate); % Get dimensions of template image

mapBlack = imSearch == 0; % Obtain a map of where the black pixels are in the template
numPixelsCompare = sum(mapBlack(:)); % Need to know how many pixels are valid for comparison

% Obtain area of searching within the search image
startSearchRows = 1 + floor(rowsSearch/2);
endSearchRows =  rowsSearch - floor(rowsSearch/2);
startSearchCols = 1 + floor(colsSearch/2);
endSearchCols = colsSearch - floor(colsSearch/2);

% Need half the dimensions of each for the template dimensions... you will
% see why we need this later
rowsTempHalf = floor(rowsTemp/2);
colsTempHalf = floor(colsTemp/2);

% Where we will store our NCC calculations
NCCMap = zeros(rowsSearch, colsSearch);

% Because you want to include all of the black pixels in your
% calculations, and these are all the same, the signal you are comparing
% to basically consists of all white pixels.
% Create a vector that consists of all 1s that is the same size as how
% many black pixels exist in the template
compareSignal = ones(numPixelsCompare, 1);

% For each location in the search image (ensuring that the full template
% is inside the image)
for i = startSearchRows : endSearchRows
     for j = startSearchCols : endSearchCols
          % Grab an image patch that is the same size as the template
          % At each location (i,j) this serves as the CENTRE of the image
          % patch, and we are grabbing pixels surrounding this centre that
          % will create a patch that is the same size as the template
          searchBlock = imSearch(i-rowsTempHalf:i+rowsTempHalf, ...
                                 j-colsTempHalf:j+colsTempHalf);

          % If all of the pixels are white, skip
          if (all(searchBlock == 1))
              continue;
          end

          % Extract only those pixels that are valid in the template
          searchPixels = searchBlock(mapBlock);

          % Must invert so that black pixels become white 
          % You mentioned that white pixels are "background"
          searchPixels = ~searchPixels;

          % Compute NCC for this patch
          NCCMap(i,j) = compareSignal'*searchPixels / ...
                        (sqrt(compareSignal'*compareSignal) * sqrt(searchPixels'*searchPixels));
     end
end

If you're a bit confused with the way I calculated the NCC, it is basically what you're used to, but I used vector algebra to compute it instead. This should hopefully give you what you want. To find the best location of where the template matched, you can do the following to extract the row and column of this location:

 [r,c] = find(NCCMap == max(NCCMap(:)));

I hope this solves your question. It is a tad inefficient, and it will really start to suffer with higher resolution images, but I wanted to give you a good start so you're not sitting around idle trying to figure it out on your own.

NB: I have not tested this code yet as I don't have an example search image that you are using to solve this problem. Hopefully this will work. Leave a comment and let me know how it goes.

rayryeng
  • 102,964
  • 22
  • 184
  • 193
  • Thanks for answering :) what I wanna do is exactly what normxcorr2 does, but only for the black pixels(0's) of my picture. So if my template was the one in the link, it would return 1 if there were black pixels on the border, regarding what the white pixels had. – Chris Post May 02 '14 at 10:18
  • Im getting an error that Matrix dimensions must agree. At line "out = corr2(template, block);" – Chris Post May 02 '14 at 11:20
  • Oh really? If that's the case then I misunderstood your post completely. So you want to do template matching only along those pixels that are black? This template is a rectangle with black pixels along the border.... so should you only include those pixels that are black in the template when you're matching? I need to be very clear before I go and edit my post. Don't downvote btw! I misunderstood. – rayryeng May 02 '14 at 14:19
  • Dont worry bout the downvote,maybe i didnt make myself clear.yes i want to template match only for black pixels,meaning if the template goes over a part of the image that has a border like the one i showed then the corresponding coordinates at the resulting matrix would be 1 whatever the inside(meaning i want to ignore any white pixels) .if (:,1)=0 and (1,:)=0 then it should be 0.5 and so on – Chris Post May 02 '14 at 17:07
  • "meaning if the template goes over a part of the image that has a border like the one i showed then the corresponding coordinates at the resulting matrix would be 1 whatever the inside"... I'm sorry this doesn't make any sense to me. Can you please elaborate? I'm sorry to keep asking you questions but I'm trying to understand the scope of this problem before I modify my post. – rayryeng May 02 '14 at 20:17
  • Ok sorry for my mistakes :) So I have this template that is a box. It has black pixels all across the first row,first column,last row,last column(as can be seen in the link in my post). I want my template matching algorithm to be able to do what normxcorr2 does, but only take into consideration black pixels, and ignore everything else. In this way, when I plug in the template mentioned before, if at some point of my image there are black pixels all across the first row and the first column , the output matrix value at the corresponding coordinate will be 0.5 WHATEVER the other pixels in middle – Chris Post May 02 '14 at 21:01
  • I hope you understand what I mean, the template is only the black pixels and not the white pixels, white pixels are like background pixels. Its the same as having a black "S" and wanting to find it in a large text but not caring about the white background since you might have other letters around them. Hope this example helps and sorry for my mistakes :) – Chris Post May 02 '14 at 21:04
  • OK. That makes more sense. Thank you for clarifying. I will start editing my post. – rayryeng May 02 '14 at 21:05
  • Thanks , this approach pretty much solved my question :) I might implement in C in order to improve the time it takes to go through all the loops ! – Chris Post May 07 '14 at 10:55
  • Good idea! Consider writing a MEX wrapper. This allows you to call C code within MATLAB. You pass it whatever variables you want to the wrapper from MATLAB, you access those variables in C then return the results to MATLAB. This tutorial by Shawn Lankton is awesome to get you started: http://www.shawnlankton.com/2008/03/getting-started-with-mex-a-short-tutorial/ – rayryeng May 07 '14 at 13:59
  • @ChrisPost: I have answered a similar post here: http://stackoverflow.com/questions/24185744/matching-object-outer-shape-using-normalized-cross-correlation/24190910#24190910 . This performs the correlation above but **without for loops**. This may help you further. – rayryeng Jun 13 '14 at 05:08