1. Field of the Invention
The present invention relates to a pattern identifying apparatus and a pattern identifying method which use, for example, accumulated information, and a program for causing a computer to perform the pattern identifying method.
2. Description of the Related Art
In the information processing field, multidimensional arrangement information is frequently used. In particular, in an image process, a partial process concerning image recognition, image synthesis or the like, a statistical process and the like, a sum total value of the elements in a specific area is often obtained and used. In the field of computer graphics, for example, a concept called a rectangular summed-area table concerning accumulated information to original input image information has been proposed (for example, see F. C. Crow, “Summed-Area Tables for Texture Mapping”, Computer Graphics, 1984). In this literature, the summed-area table is set to a two-dimensional arrangement having the same size (the same number of elements) as that of the input image, and the pixel value of the coordinates (x, y) of the input image is defined as I(x, y). Then, a component C(x, y) of the same position (x, y) on the summed-area table is defined by the following expression (1).
                              C          ⁡                      (                          x              ,              y                        )                          =                              ∑                                                            x                  ′                                ≤                x                                                              y                  ′                                ≤                y                                              ⁢                      I            ⁡                          (                                                x                  ′                                ,                                  y                  ′                                            )                                                          (        1        )            
That is, in FIGS. 7A and 7B, the sum total value of the pixels in the rectangle having the pixels of the origin position (0, 0) and the position (x, y) as the opposing corner in an original input image illustrated in FIG. 7A is equivalent to the value C(x, y) of the position (x, y) on the summed-area table illustrated in FIG. 7B. Incidentally, although the summed-area table originally described in the above literature has the origin position as the lower left of the image, the origin position is hereinafter assumed as the upper left of the image for consistency with the following description.
By the above definitions, it is possible to obtain the sum of I(x, y) in an arbitrary rectangular area set horizontally or vertically on the input image, only by referring to the four points on the summed-area table. For example, as illustrated in FIG. 8, the following expression (2) is used to obtain the sum total C(x0, y0; x1, y1) of the pixel values in the rectangular area having (x0, y0) and (x1, y1) as the opposing corner.C(x0,y0;x1,y1)=C(x0−1,y0−1)−C(x0−1,y1)−C(x1,y0−1)+C(x1,y1)  (2)
Thus, it is possible to obtain at high speed the sum total of the values in the arbitrary rectangular area on the image.
Besides, Japanese Patent Application Laid-Open No. 2008-299627 discloses one of accumulated information implementation methods.
In the field of image recognition, accumulated information which is equivalent to the above summed-area table is called Integral Image, feature quantities are calculated in a plurality of local areas by using the Integral Image, and the pattern recognition is performed based on the calculated feature quantities (for example, see P. Viola, M. Jones, “Rapid Object Detection using a Boosted Cascade of Simple Features”, Proc. IEEE Conf. on Computer Vision and Pattern Recognition, Vol. 1, pp. 511-518, December 2001). Here, the “local area” indicates a partial area of the image area cut out from the input image. In the pattern recognition, the feature quantities are calculated in the plurality of local areas, and parameters previously obtained by learning are used for the feature quantities. Here, it should be noted that the parameters include information such as positions, sizes and the like of the local areas for which the feature quantities are calculated.
Further, in the pattern recognition, the number of times of referring to the local areas is very large, and the accumulated information is randomly read for calculating the feature quantities. For example, in a case where the accumulated information is stored in a single-port memory in which one data can be read at a time, readings of four vertexes are serialized and processed by four-time memory accesses. Here, if one cycle is necessary for the one-time memory access, at least four cycles are necessary to obtain one rectangular area. For this reason, in a case where requested detection performance (depending on a frame rate, an image size, the number of detection targets, and the like) is high, there is a possibility that the memory accesses become a bottleneck. Consequently, to achieve the high-performance detection, it is required to be able to process whole or a part of the serialized four-time readings in parallel.
As one method of cutting down such a reading time, there is a method of storing accumulated information in a dual-port memory in which two data can be read at a time, and thus cutting down the reading time. As another method, there is a method of previously writing same accumulated information in four single-port memories, and then reading four vertexes respectively from the four memories in parallel. As yet another method, there is the method of reducing the number of readout times themselves as disclosed in Japanese Patent Application Laid-Open No. 2008-102792.
As yet another method, there is a method of previously writing an integral image in a plurality of storages according to a predetermined rule, and then enabling to read the written images in parallel. In this method, it is possible to read the four vertexes of the integral image in parallel by previously limiting the shape of a local area at the time of learning. Thus, it is possible to eliminate the bottleneck in memory access and achieve an apparatus capable of performing high-speed reading.
Further, there has been proposed a method by which, to improve recognition accuracy, an area to be referred to in a feature quantity calculating process is read with a shape illustrated in FIG. 13 (for example, see S. Yan, S. Shan, X. Chen, and W. Gao. Locally assembled binary (lab) feature with feature-centric cascade for fast and accurate face detection. 26th IEEE Conference on Computer Vision and Pattern Recognition, CVPR, 2008). More specifically, in the reference area illustrated in FIG. 13, blocks 1550 to 1558 respectively having the same width and height are arranged like tiles, and the feature quantity is calculated from the sum total of pixels in each block. That is, it only has to read 16 points of vertexes 1501 to 1516 of each block by using the integral image, and calculate the sum total based on the read points. However, in this case, it is necessary to perform the memory reading four times as much as the conventional four-vertex memory reading of the local area. Further, if the shape of the local area is limited for the purpose of a high-speed process, recognition accuracy may be influenced by such a limitation. Therefore, it is also necessary to reduce the limitation as much as possible in order to improve recognition accuracy.