matlab template matching only for 0 (or 1) in matrix

Question

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

Answer 1

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.