19th LSI Design Contests・in Okinawa  Design Specification - 3-2

3-2. Algorithm

The algorithm of the person detection using template matching based on the program that was designed in MATLAB® is shown below.
 In addition, it was created and verified using MATLAB®R2012a (7.14.0.739).


  • m file:Template_matching_en.m
  • Original image:original.png
  • Template image:template.png

  • (1)Input image
    Input the search image and the template image.

    (2)Grayscaling and binarization
    Since the template matching using a color image is difficult, the search image and the template image is binarized after converting into grayscale in the following way.

    ・Grayscaling
    We use the NTSC Coef. method to grayscale of the image. The NTSC Coef. Method, in one method of converting from a color image to 256-level gray scale image, it can be calculated by the following equation.

    Y=0.298912*R+0.586611*G+0.114478*B


    Coefficients of this equation are obtained from the human visual characteristics experimentally for the color.

    ・Binarization
    To binarizing the gray- scale image, it is necessary to determine the threshold. First, obtain the histogram of the search image. Threshold is value the total number of low brightness pixel is half of total pixel. If the pixel value is smaller than the threshold value, the pixel of the image is white. If this is not the case the pixel of image is black.

    (3)Matching method
    It calculated the SAD by the template matching. Since binarization processing was performed, SAD is the sum of exclusive OR of the pixel value of the template image and the search image. To move the template images in the order from the upper left to the lower right, to obtain the SAD at each location.

    (4)Drawing matching points
    The resulting SAD and the threshold are compared. Mark the portions that SAD is lower than the threshold. This time threshold is 500. If different number of pixels that the value of the search image and the template image is within 500, let me be the search image and the template image is consistent.

    (5)Output
    Output the resulting image marked the matched portions..


    The flowchart of the algorithm is shown in Fig 1.

    Figure 1

    Fig 1:Flowchart of template matching

    Reference

    [1] CodeZine 開発者のための実装系Webマガジン “テンプレートマッチング法を用いた顔画像の検出”
        http://codezine.jp/article/detail/86

    [2] 中山 謙二,金沢大学“テンプレートマッチングによる顔検出”
        http://leo.ec.t.kanazawa-u.ac.jp/~nakayama/

    <<Back                 Next>>