JP2010134692A - Information processor and information processing method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide an information processor, an information processing method or the like, reducing an array (memory) in processing of accumulation information. <P>SOLUTION: Firstly, a processing object image is divided to predetermined areas (divided areas), and accumulation information for pixel value (divided area accumulation information) is calculated for each divided area (step S41). A total sum of pixel values in a specific area (rectangular area) regulated on the processing object image (specific area total sum value) is then determined by use of the divided area accumulation information (step S42). <P>COPYRIGHT: (C)2010,JPO&INPIT

Description

  The present invention relates to a filter operation for obtaining the sum and average of signal values in a rectangular area, and an information processing apparatus and information processing method suitable for pattern identification using such a filter operation.

  In the field of information processing, multidimensional arrays are frequently handled. Among them, the sum of elements within a specific range is often obtained. Non-Patent Document 1 describes the concept of rectangular accumulated information (summed-area table) regarding computer graphics processing. Cumulative information is data such that the element value at an arbitrary point is the sum of the pixel values in a region whose diagonal is the origin of the original image and the arbitrary point.

  Here, a process of calculating the sum of the pixel values in the rectangular area using the accumulated information will be described with reference to FIG. FIG. 13 is a diagram illustrating an example of accumulated information. In this example, the origin is the upper left point of the original image. Element 1 in FIG. 13 has the sum of the pixel values of all the pixels included in area A in the original image as the element value. For this reason, the sum of the pixel values of all the pixels included in the region D in the original image is calculated by subtracting the element values of element 2 and element 3 from the element value of 4, and adding the element value of element 1 . That is, the sum of the pixel values of the rectangular area in the original image can be obtained at high speed by adding / subtracting the data values at the four corners of the rectangular area, using accumulated information.

  That is, when the pixel value of the input image is defined as I (x, y) and the cumulative information C (x, y) is defined as shown in Equation 1, I (x in an arbitrary rectangular area placed in the input image , Y) can be obtained simply by referring to the four points on the accumulated information using the equation shown in equation (2).

Here, (x ₀ , y ₀ ) is the upper left vertex coordinates of the rectangle, and (x ₁ , y ₁ ) is the lower right vertex coordinates. By such processing, the sum of the values in the rectangular area on the image can be obtained at high speed. However, the coordinates start from 0, and C (x, −1) and C (−1, y) are 0.

  Further, in the field of image recognition, Non-Patent Document 2 describes that high-speed face detection is performed using cumulative information (Integral Image) as described above.

Crow, "Summed-Area Tables For Texture Mapping", Computer Graphics, Vol. 18 (3), pp. 207-212, July 1984. 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.

  The element value of such accumulated information increases monotonously as it goes away from the origin of the original image and toward the lower right in the example shown in FIG. Therefore, when the accumulated information is to be stored in the array (memory), the array has the lower right data value (the accumulated information value at the position farthest from the upper left, which is the origin of the original image, that is, the accumulated information). Must have a bit width that can be stored.

  In this case, the larger the size of the original image, the greater the number of digits of the accumulated information, and therefore the bit width of the array necessary to store the accumulated information becomes larger. As a result, the size of the entire array becomes enormous. Become.

  In response to this problem, Non-Patent Document 1 divides an original image, calculates cumulative information in units of the divided original images, and at the same time, accumulates values from the origin of the original image to the origin of the divided image in another array. Is stored.

  However, in order to perform such processing, an array (memory) for storing the accumulated value is separately required.

  An object of the present invention is to provide an information processing apparatus, an information processing method, and the like that can reduce an array (memory) when handling accumulated information.

  As a result of intensive studies to solve the above problems, the present inventor has come up with various aspects of the invention described below.

  An information processing apparatus according to the present invention includes a dividing unit that divides processing target information of a multidimensional array into a plurality of divided regions, and a predetermined information of the divided regions as accumulated information values corresponding to each element position in the processing target information. Calculating means for calculating, for each of the divided regions, a total value of all the element values in a region diagonally corresponding to the origin position of each element position of the processing target information belonging to the divided region. Features.

  An information processing method according to the present invention includes a dividing step of dividing processing target information in a multidimensional array into a plurality of divided regions, and a cumulative information value corresponding to each element position in the processing target information. A calculation step of calculating, for each of the divided regions, a total value of all element values in a region whose diagonal is the origin position of each of the processing target information belonging to the divided region. Features.

  ADVANTAGE OF THE INVENTION According to this invention, the increase in the number of digits of accumulation information at the time of calculating the accumulation information of the process target information which is a two-dimensional or more multidimensional array can be suppressed. For this reason, it is possible to reduce the capacity of the buffer for storing the accumulated information and to reduce the scale of the arithmetic circuit using the accumulated information.

  Hereinafter, embodiments of the present invention will be specifically described with reference to the accompanying drawings.

(First embodiment)
First, a first embodiment of the present invention will be described. FIG. 1 is a block diagram showing the configuration of the information processing apparatus according to the first embodiment of the present invention. In the present embodiment, as information processing, image processing for calculating the sum of pixel values in a rectangular area is performed. Also, cumulative information is used when calculating the sum of pixels in the rectangular area.

  As shown in FIG. 1, the information processing apparatus according to the first embodiment includes a CPU 101, an information input unit 102, a DMA controller (DMAC) 103, a processing target information storage memory 104, a bus 105, and a cumulative information calculation processing unit 100. Is provided. The CPU 101 may also serve as the cumulative information calculation processing unit 100.

  The CPU 101 controls each unit connected via the bus 105 and realizes a desired process intended by the information processing apparatus.

  The information input unit 102 inputs multi-dimensional processing target information. For example, input image data to be processed is taken into the apparatus. The information input unit 102 may be configured by an image sensor such as a CCD, or may be an I / F device that receives data to be processed from an external device through a predetermined communication path such as a network.

  The processing target information storage memory 104 is configured by a storage device such as a ROM, RAM, or HDD, and is connected to the bus 105. The processing target information storage memory 104 is used as an area for holding processing target information. Also, a program code indicating the operation content of the CPU 101 may be stored, or a work area (not shown) in which various processes are performed may also be used. Here, the processing target information is, for example, image data. In this embodiment, as shown in FIG. 5, image data having a size of 256 pixels × 256 pixels and a pixel value represented by 8 bits is processed. Assume that it is stored in the target information storage memory 104.

  When the CPU 101 sets and issues an operation command, the DMA controller 103 independently and continuously controls data transfer of a predetermined size among the information input unit 102, the processing target information storage memory 104, and the cumulative information calculation processing unit 100. To do. When the commanded transfer operation is completed, an interrupt signal is notified to the CPU 101 via the bus 105.

  The cumulative information calculation processing unit 100 is provided with a bus I / F 110 connected to the bus 105, a cumulative information generation unit 111, a cumulative information use calculation unit 112, a cumulative information holding unit 113, and a division control unit 114.

  As will be described in detail later, the cumulative information holding unit 113 is provided with a cumulative information holding memory that holds cumulative information and a memory controller that controls input and output to this memory, as shown in FIG.

  The cumulative information generation unit 111 generates cumulative information (cumulative information value corresponding to each element position in the processing target information) of the processing target image input from the information input unit 102 and stored in the processing target information storage memory 104. The accumulated information is stored in the accumulated information holding unit 113. At this time, based on the control by the division control unit 114, not the simple accumulated information but the divided area accumulated information is calculated. Here, each image obtained by dividing the processing target image is referred to as a divided region, and the divided region cumulative information refers to cumulative information that is calculated for each divided region by dividing the processing target image into divided regions. In the present embodiment, the image information stored in the processing target information storage memory 104 is sent pixel by pixel to the cumulative information calculation processing unit 100 in raster scan order under the control of the CPU 101, and the cumulative information generation unit 111 Divided region cumulative information is calculated for the image information. Details of the cumulative information generation unit 111 will be described later with reference to FIG.

  The cumulative information use arithmetic unit 112 performs arithmetic processing using the area division cumulative information held in the cumulative information holding unit 113 in accordance with a request from the CPU 101, and returns the result to the CPU 101. The details of the accumulated information use calculation unit 112 will be described later with reference to FIG.

  In the division control unit 114, division parameters are set in advance. The division parameter is a parameter that defines how to divide the processing target image. For example, in the present embodiment, as shown in FIG. 5, the division parameter stipulates that the size of 64 pixels × 64 pixels is used as a unit to divide all into divided areas of the same size. The format of the division parameter is arbitrary as long as the division state can be expressed. The division parameter is set in the division control unit 114 in advance by some means (for example, the CPU 101).

  Then, the division control unit 114 outputs the division boundary information to the cumulative information generation unit 111 and the cumulative information use calculation unit 112 according to the division parameter. The format of the division boundary information is arbitrary as long as the division state can be expressed. For example, in this embodiment, as shown in FIG. 5, for each of the x coordinate and the y coordinate, 64 before (between 63 and 64), 128 before (between 127 and 128), and 192 The information that the division is performed in the vertical direction and the horizontal direction at the front (between 191 and 192) is the division boundary information.

  Here, the details of the cumulative information generation unit 111 will be described with reference to FIG. FIG. 2 is a block diagram illustrating a configuration of the cumulative information generation unit 111 and a connection relationship between the bus I / F 110 and the cumulative information holding unit 113.

  As shown in FIG. 2, the accumulated information generation unit 111 includes an input information size storage register 201, an address counter 202, an input element value holding register 203, a horizontal direction accumulated value holding register 204, and a previous line accumulated information value reference register 205. Is provided. Furthermore, a cumulative addition processing unit 206 and an initialization control unit 207 are also provided.

  The input information size storage register 201 stores the size of multi-dimensional array information (for example, two-dimensional image information) input from the information input unit 102, and the value before the processing is started by the CPU 101 via the bus I / F 110. Is set.

  The input element value holding register 203 temporarily holds one element value (for example, pixel value) of the input array information input by the control of the CPU 101 or the DMAC 103 via the bus I / F 110 in order. In the present embodiment, as described above, the image information stored in the processing target information storage memory 104 is sent to the cumulative information calculation processing unit 100 pixel by pixel in the raster scan order.

  Based on the size of the input array information stored in the input information size storage register 201, the address counter 202 stores a cumulative information value that is generated corresponding to each input of an element value to the input value holding register. The memory address of the power accumulation information holding unit is calculated. When the first pixel (origin position) of the input information is input, the address to be stored is reset to 0 or a predetermined offset value, and the storage destination address is incremented by 1 until the end pixel of the image is input thereafter.

  Further, the address counter 202 refers to the size of the input array information stored in the input information size storage register 201, and positions of pixels sent from the processing target information storage memory 104 in the raster scan order (on the processing target information top). (Coordinates) is calculated. Then, the address counter 202 outputs the calculated input pixel value coordinates to the initialization control unit 207. Further, the address counter 202 calculates the previous line accumulated information address in which accumulated information of the same line position one line before is stored when the input pixel is in the second and subsequent lines. This is obtained by subtracting the number of elements in one line from the previously calculated storage destination address. The address calculated by the address counter 202 is given to the memory controller 113-2 in the cumulative information holding unit 113, and writing or reading to the address of the cumulative information holding memory 113-1 in the cumulative information holding unit 113 is performed. Is called.

  The previous line accumulated information value reference register 205 temporarily holds the accumulated information value read from the accumulated information holding memory 113-1, using the previous line accumulated information address calculated by the address counter 202. However, if the initialization control unit 207 outputs an initialization instruction, 0 is set in the previous line accumulated information value reference register 205 regardless of the accumulated information value read from the accumulated information holding memory 113-1. Is done.

  The horizontal cumulative value holding register 204 holds cumulative addition information from the first pixel in the divided area for only one line in the divided area to which the currently input pixel belongs. When a pixel is input to the input element value holding register 203, the cumulative added value of the pixel up to the previous time is held. This register value is held only for one line in the divided area to which the input pixel belongs. Therefore, when the input pixel exceeds the divided area or becomes the next line, the horizontal direction accumulated value holding register 204 is set to 0 by the initialization instruction from the initialization control unit 207. .

  The initialization control unit 207 uses the division boundary information sent from the division control unit 114 to instruct the horizontal direction accumulated value holding register 204 and the previous line accumulated information value reference register 205 to perform initialization. This is because the cumulative information calculation processing unit 100 does not calculate one piece of cumulative information, but cumulative information calculated for each divided region (divided region cumulative information).

  The initialization control unit 207 instructs the previous line accumulated information value reference register 205 to perform initialization when the input pixel is a pixel belonging to the uppermost line of each divided region, and the previous line accumulated information value reference register 205 The information value reference register 205 is set to 0. On the other hand, when the input pixel is a pixel belonging to the leftmost column of each divided area, the horizontal direction cumulative value holding register 204 is instructed to initialize, and the horizontal direction cumulative value holding register 204 is set to 0. To.

  In the cumulative addition processing unit 206, adders 206-1 and 206-2 are provided. The adder 206-1 performs addition to Equation 3, and the adder 206-2 performs addition shown in Equation 4. Here, I (x, y) represents the pixel value of the input image, C (x, y) represents accumulated information, and S (x, y) represents the accumulated pixel value in the horizontal direction at a certain vertical coordinate y. Indicates the value. However, the coordinates start from 0 (the origin is the upper left of the image), and S (0, y) = I (0, y) and C (x, 0) = S (x, 0) are satisfied (that is, S (-1, y) and C (x, -1) are 0). The reason why the initialization control unit 207 instructs the above initialization is to perform such setting for setting S (-1, y) and C (x, -1) to 0 for each divided region. It is.

  That is, the adder 206-1 performs addition of the horizontal direction accumulated value and the input pixel value. The added result is fed back and stored in the horizontal direction cumulative value holding register 204 as a new horizontal direction cumulative value and used when the next pixel is input.

  The adder 206-2 adds the output of the adder 206-1 and the divided area accumulated information value held in the previous line accumulated information value reference register 205. This addition result becomes the divided area accumulated information value corresponding to the input pixel position, and is stored in the storage address calculated by the address counter 202 of the accumulated information holding memory 113-1 via the memory controller 113-2.

  Next, the operation of the cumulative information generation unit 111 configured as described above, that is, the calculation procedure of cumulative information will be described. In the cumulative information generation unit 111, the cumulative information is sequentially calculated mainly by the operations of the adders 206-1 and 206-2.

  However, when the divided region accumulation information is calculated by the addition of Equation 3 and Equation 4, the horizontal pixel value accumulation value S is initially set at the vertical division boundary (the boundary indicated by the arrow A in FIG. 5). Turn into. That is, the initialization control unit 207 sets S (64, y) = I (64, y), S (128, y) = I (128, y), and S (192, y) = I (192, y)). Similarly, the accumulated information value C is initialized at a horizontal division boundary (a boundary indicated by an arrow B in FIG. 5). That is, the initialization control unit 207 sets C (x, 64) = S (x, 64), C (x, 128) = S (x, 128), and C (x, 192) = S (x, 64). 192)).

  Thus, when calculating the divided region accumulated information, it is necessary to initialize the horizontal direction accumulated value (S) and the accumulated information value (C) at the vertical direction divided boundary and the horizontal direction divided boundary, For this purpose, the division boundary information received from the division control unit 114 is used.

  Next, the configuration and operation of the cumulative information use calculation unit 112 will be described with reference to FIG. FIG. 3 is a block diagram illustrating the configuration of the accumulated information use calculation unit 112 and the connection relationship between the bus I / F 110 and the accumulated information holding unit 113. In the present embodiment, as described above, as the content of the image processing using the accumulated information, the sum of the pixel values in the rectangular area is calculated.

  As shown in FIG. 3, the accumulated information use calculation unit 112 includes a specific area designation register 301, a reference address calculation unit 302, a reference value temporary holding register 303, an addition / subtraction processing unit 304, a calculation result holding register 305, and a specific area division A unit 306 is provided.

  Note that the input information size storage register 201 is in the cumulative information generation unit 111, and as described above, the size of the input information is preset by the CPU 101 via the bus I / F 110 before the generation of the cumulative information. Yes.

  The specific area designation register 301 holds designation of a specific area (for example, a rectangular area) for which the sum of pixel values performed by the CPU 101 is to be obtained. Designation of a specific area means designation of coordinates necessary for defining the shape of the specific area. Therefore, when the specific area is a rectangular area, the CPU 101 sets the diagonal coordinates of two points representing the rectangular area in the specific area specifying register 301 via the bus I / F 110. In the present embodiment, as shown in FIG. 5, it is assumed that a rectangular area having the coordinates (80, 160) and the coordinates (223, 207) as diagonal coordinates is designated as the specific area. Therefore, the coordinates (80, 160) and the coordinates (223, 207) are set in the specific area designation register 301.

  The specific area dividing unit 306 divides the specific area specified by the specific area specifying register 301 according to the division boundary information sent from the division control unit 114. In the present embodiment, since the accumulated information is calculated for each divided area, the specific area dividing unit 306 divides the specific area according to the divided areas. The specific area divided according to the divided area is referred to as a divided specific area. In addition, for each divided specific area, the total sum of the pixel values in the divided specific area is calculated as the second calculation means by using the divided area accumulated information of the corresponding divided area. Furthermore, the sum total of each divided specific area is summed to calculate the sum of the pixel values in the specific area. The specific area dividing unit 306 calculates coordinates necessary for calculating the sum of the pixel values in the divided specific areas according to the division boundary information sent from the division control unit 114.

  In this embodiment, since the specific area is a rectangular area and the divided area is also a rectangular area, the divided specific area is also a rectangular area. If the coordinates of the four corners of the rectangle are known as described above, the sum of the pixel values in the rectangular area can be obtained using the corresponding cumulative information values (cumulative information values) of the four points. Accordingly, the specific area dividing unit 306 calculates the diagonal coordinates of each of the two points in the divided specific area. In the present embodiment, as shown in FIG. 5, as the diagonal coordinates of two points in the divided specific area, combinations of (80, 160) and (127, 191), (128, 160) and (191, 191) Combination, (192,160) and (223,191), (80,192) and (127,207), (128,192) and (191,207), and (192,192) And the combination of (223, 207). Hereinafter, the divided specific areas represented by these two diagonal coordinates are referred to as divided specific areas A to F in order.

  The reference address calculation unit 302 calculates an address for referring to the accumulated information using the two diagonal coordinates calculated for each divided specific region by the specific region dividing unit 306. For example, the divided specific area A has four corners at the upper left (80, 160), upper right (127, 160), lower left (80, 191), and lower right (127, 191). Therefore, the reference address calculation unit 302 calculates an address that stores accumulated information corresponding to these coordinates (79,159), (127,159), (79,191), and (127,191). The addresses are sequentially transferred to the memory controller 113-2. Similar processing is performed for the other divided specific regions B to F. The accumulated information is expressed by, for example, Equation 1.

  The memory controller 113-2 accesses the accumulated information holding memory 113-1 based on the received address, and sets the accumulated information values of four points sequentially obtained for each divided specific area in the reference value temporary holding register 303. However, as shown below, when the upper boundary of the divided specific area and the upper boundary of the divided area match, and when the left boundary of the divided specific area and the left boundary of the divided area match. May be set to 0 regardless of the accumulated information value obtained by referring to the accumulated information holding memory 113-1. This is because the information stored in the accumulated information holding memory 113-1 is not one piece of accumulated information but accumulated information calculated for each divided area (divided area accumulated information). That is, as described above, C (x, −1) and C (−1, y) are set to 0 at the time of addition shown in Equations 3 and 4, and the same setting is applied to each divided region. To do.

  The information that the upper boundary of the divided specific area and the upper boundary of the divided area match, and the information that the left boundary of the divided specific area and the left boundary of the divided area match are specified areas. Calculated by the dividing unit 306. Then, the reference value temporary holding register 303 sets 0 to a necessary register based on this information. For the accumulated information value that is known to be set to 0, the reference to the accumulated information holding memory 113-1 can be omitted.

  Regarding the divided specific area (for example, divided specific areas D, E, and F in FIG. 5) whose upper boundary is coincident with the upper boundary of the divided area, of the four corners of the divided specific area, the corner is in contact with the upper boundary 0 is set as the cumulative information value in the register storing the cumulative information value corresponding to. For example, the divided specific area D has four corners at the upper left (80, 192), upper right (127, 192), lower left (80, 207), and lower right (127, 207). Accordingly, in order to obtain the sum of the pixel values of the divided specific region D, the cumulative information corresponding to the coordinates (79, 191), (127, 191), (79, 207) and (127, 207) is referred to. At this time, since the upper boundary of the divided specific area D and the upper boundary of the divided area match, the accumulated information values corresponding to the corners in contact with the upper boundary, that is, the coordinates (79, 191) and (127, 191). ) Is stored in the reference value temporary holding register 303 as 0.

  Similarly, with respect to a divided specific region (for example, divided specific regions B, C, E, and F in FIG. 5) whose left boundary coincides with the left boundary of the divided region, the left side of the four corners of the divided specific region In the register that stores the cumulative information value corresponding to the corner in contact with the boundary, 0 is set as the cumulative information value. For example, the divided specific region B has coordinates of four corners, that is, upper left (128, 160), upper right (191, 160), lower left (128, 191), and lower right (191, 191). Accordingly, in order to obtain the sum of the pixel values of the divided specific region B, the cumulative information corresponding to the coordinates (127, 159), (191, 159), (127, 191), and (191, 191) is referred to. At this time, since the left boundary of the divided specific area B and the left boundary of the divided area match, the accumulated information values corresponding to the corners in contact with the left boundary, that is, the coordinates (127, 159) and (127, 191). ) Is stored in the reference value temporary holding register 303 as 0.

  When the reference value temporary holding register 303 holds four values for each divided specific area, the addition / subtraction processing unit 304 executes a predetermined addition / subtraction process using the four points, and the pixel value of the divided specific area Calculate the sum of. As the predetermined addition / subtraction process, for example, a calculation process shown in Equation 1 is given. The addition / subtraction processing unit 304 calculates the sum of the pixel values of the specific area by calculating the sum of the pixel values of each of the specific areas to be divided and summing them.

  This calculation result is held in the calculation result holding register 305. The CPU 101 can know the completion of calculation by an interrupt notification or reference to a completion flag via the bus I / F 110. Then, the value of the operation result holding register 305 is acquired and used as the total value of the set rectangular area.

  Next, an image processing operation performed by the information processing apparatus configured as described above will be described. FIG. 4 is a flowchart illustrating the operation of the information processing apparatus according to the first embodiment.

  First, in step S <b> 41, the cumulative information generation unit 111 reads processing target image data stored in the processing target information storage memory 104, and creates processing target image cumulative information. At this time, the accumulation information generation unit 111 calculates division area accumulation information instead of simple accumulation information under the control of the division control unit 114. The calculated divided region accumulated information is stored in the accumulated information holding unit 113.

  Next, in step S <b> 42, the cumulative information generation unit 111 reads a necessary cumulative information value of the divided region cumulative information stored in the cumulative information holding unit 113. At this time, the cumulative information generation unit 111 calculates which cumulative information value is read from the cumulative information holding unit 113 under the control of the division control unit 114. The read accumulated information value is transferred to the accumulated information use calculation unit 112, and the accumulated information use calculation unit 112 calculates the sum of the pixel values in the specific area (for example, the rectangular area) (the total value in the specific area). .

  As described above, the image processing performed according to the present embodiment is divided into two processes, that is, a process of calculating the divided area accumulated information and a process of calculating the total value in the specific area using the calculated divided area accumulated information. It can be divided roughly.

  According to this embodiment, the size of the array (memory) for storing the accumulated information can be reduced. For example, as described above, when conventional cumulative information is created for image data whose size is 256 pixels × 256 pixels and the pixel value is represented by 8 bits, the bit width required for the cumulative information holding memory is It becomes 24 bits. On the other hand, according to the present embodiment, since the size of the divided area is 64 pixels × 64 pixels, the bit width required for the cumulative information holding memory 113-1 may be 20 bits.

  If the divided area is further reduced (for example, 32 pixels × 32 pixels), the bit width necessary for the accumulated information holding memory 113-1 can be further reduced. However, since the number of divisions of the specific area (the number of division specific areas) increases as the division area is reduced, the cumulative information holding memory 113-1 required to calculate the sum of the pixel values of the specific area. Increases the number of accesses to That is, the time required to calculate the sum of the pixel values in the specific area increases. That is, the processing time and the size of the divided area are in a trade-off relationship. Therefore, if priority is given to shortening the processing time, the divided area may be enlarged as long as the circuit size constraint allows. Conversely, if priority is given to reducing the circuit scale, as long as the processing time constraint allows, What is necessary is just to make a division area small.

  In such information processing, when the size of the specific area for calculating the sum of pixel values is known in advance, it is preferable to make the size of the divided area equal to the size of the specific area. By making these equal, it is possible to reduce the number of divisions of the specific area (the number of divided specific areas) to 4 or less regardless of the position of the specific area set on the detection target image. This is because it becomes easy.

  Similarly, when there are a plurality of sizes to be set as specific areas, the number of divisions (number of divided specific areas) of the specific area is 4 or less if the largest one of them is made equal to the size of the divided areas. Therefore, scheduling of processing becomes easy.

  Further, by applying this embodiment, face detection as shown in Non-Patent Document 2 can also be performed.

  In Non-Patent Document 2, as shown in FIG. 6, a region called a processing window 601 is moved in the processing target image 600, and it is determined whether or not a face is included in each movement destination processing window. Yes. In this determination, the sum of the pixel values in a specific rectangular area is obtained for a number of rectangular areas 602 within each processing window 601 at each movement destination.

  When the present embodiment is applied to such processing, the specific area corresponding to the rectangular area 602 may be designated many times for the specific area specifying register 301 in the accumulated information utilization calculating unit 112.

  When performing such processing, as described above, the size of the divided area is set to the maximum size of the rectangular area 602 (in Non-Patent Document 2, a plurality of rectangular areas 602 having different setting positions and sizes are prepared. It is preferable to be equal to As described above, no matter where the specific area is set on the detection target image, the number of divisions of the specific area (the number of divided specific areas) can be reduced to 4 or less, and the process scheduling is easy. Because it becomes.

  Further, when the size of the processing window 601 is compared with the maximum size of the rectangular area 602, they are the same or the processing window 601 is larger. Therefore, the same effect can be obtained even if the size of the divided area is equal to the size of the processing window 601.

(Second Embodiment)
Next, a second embodiment of the present invention will be described. As described above, according to the first embodiment, face detection can be performed by calculating in advance the divided region accumulated information over the entire processing target image and storing it in the accumulated information holding memory 113-1. . The second embodiment is intended to further reduce the capacity of the accumulated information holding memory 113-1 when performing such processing. FIG. 7 is a flowchart showing the operation of the information processing apparatus according to the second embodiment (operation when the divided region accumulated information is held by the band buffer). FIG. 8 is a diagram showing a state of a band buffer that is temporarily held for the entire divided region accumulated information in the second embodiment. Here, for simplification of explanation, it is assumed that the size of the divided area is equal to the size of the processing window.

  First, in step S91, the cumulative information generation unit 111 generates divided region cumulative information only for the band region 702 having a predetermined height located at the head, and stores it in the cumulative information holding memory 113-1 in the cumulative information holding unit 113. , The divided area accumulation information of the band area 702 is stored.

  Next, in step S92, when the processing window is at the head (left end) position 701 of the band, the cumulative information generation unit 111 performs processing for obtaining the sum of the pixel values in a specific rectangular area in the processing window. Do this for many rectangular areas. Then, the processing window is moved to the position shifted by one pixel to the right from the head position 701, and the same processing is performed again. Thereafter, the same processing is repeated while shifting the processing window until the processing window reaches the right end of the band region 702.

  In this way, in steps S91 to S92, the divided area cumulative information corresponding to the band size is calculated for a predetermined band position, and the total in the specific area is calculated using the calculated divided area accumulated information.

  When the calculation of the sum in the specific area for one band area (step S72) is completed, the cumulative information generation unit 111 determines whether or not the band area currently being processed is a position including the final line of the input information in step S93. Determine in.

  If it is not the last line position, in step S94, the divided area cumulative information for the next one line is generated and held by the same processing as in step S91. Since the band buffer in this embodiment is configured as a line-by-line ring buffer, when generating a new line, the oldest one line is discarded and a new line is held in this area. At this time, since the divided area accumulated information for the previous line already exists on the band buffer of the accumulated information holding memory, accumulated information for one line can be generated by the same processing as in the first embodiment. That is, in this calculation, there is no overhead due to the band buffer. That is, it is necessary to convert which address in the current buffer corresponds to the desired position of the divided region accumulated information, but there is almost no processing overhead compared to the case where the entire area is held at once.

  After the next line is generated / held, the accumulated information is moved to the band area 703, and the accumulated information generating unit 111 executes the process of step S92 again. Thereafter, the same processing is repeated while moving the band area downward line by line until it is determined as the last line in step S93.

  As described above, in steps S92 to S94, after the calculation of the sum within the specific area in the first band is completed, the band position is slid downward by one line, and the previously calculated divided area accumulation information is obtained with respect to the band position. The divided area accumulated information for one line to be added is calculated. Then, the divided area accumulated information for one line calculated this time is replaced with the oldest one line of the divided area accumulated information calculated so far, thereby obtaining divided area accumulated information for the current band position. Subsequently, the sum in the specific area is calculated using the divided area accumulation information for the current band position.

  If it is determined in step S93 that the final line has been reached, the process is completed.

  As described above, in this embodiment, the band area 702 is a band area having a predetermined height that is temporarily held in the accumulated information holding memory 113-1, and the accumulated information holding memory 113-1 is once at a band area 702. Only the accumulated information of the divided area of the size is stored. The predetermined height of the band area 702 is equal to the height of the processing window area of the face detection process, and the width is equal to the width of the processing target image information.

  Further, in the present embodiment, the calculation of the sum in the specific area is performed for each band area.

  In the present embodiment, any size can be used as long as it can store the divided area accumulated information having the size of the band area 702 as the size of the accumulated information holding memory 113-1. On the other hand, in the first embodiment, as the size of the cumulative information holding memory 113-1, a size capable of storing the divided region cumulative information 700 is required. That is, according to the present embodiment, it is possible to significantly reduce the memory capacity of the cumulative information holding memory 113-1 as compared with the first embodiment, with almost no computation overhead.

  As in the first embodiment, the processing target image is image data having a size of 256 pixels × 256 pixels and a pixel value represented by 8 bits, and the processing window size (= divided area size) is 64 pixels × 64. In the case of pixels, the size that needs to be held at one time is one band. Therefore, the size (depth) of the accumulated information holding memory to be prepared at a minimum is 64 × 256. On the other hand, in the first embodiment, the required accumulated information holding memory size (depth) is 256 × 256. Note that the width of the accumulated information holding memory is 20 in any of the embodiments.

(Third embodiment)
Next, a third embodiment of the present invention will be described. In the third embodiment, the buffer capacity is further reduced. FIG. 9 is a flowchart showing the operation of the information processing apparatus according to the third embodiment (operation when the divided region accumulated information is held by the block buffer). FIG. 10 is a diagram illustrating a state of a block buffer that is temporarily held for the entire divided region accumulated information in the third embodiment. Again, for the sake of simplicity of explanation, it is assumed that the size of the divided area is equal to the size of the processing window. The block buffer is configured as a ring buffer in units of vertical line segments. Here, the vertical line segment is a line segment having a length that matches the processing window height.

  First, in step S1101, the cumulative information generation unit 111 sets the upper left of the processing target image as the origin 1005 for calculating the divided region cumulative information.

  Next, in step S1102, the accumulated information generation unit 111 generates and stores divided area accumulated information of a block including the current origin at the upper left. That is, accumulated information of the area 1001 in FIG. 10 is generated.

  After that, in step S1103, the cumulative information generation unit 111 performs a process for obtaining the sum of the pixel values in a specific rectangular area on a large number of rectangular areas in the processing window.

  Subsequently, in step S1104, the cumulative information generation unit 111 determines whether the processed processing window position has reached the rightmost column.

  If the rightmost column has not been reached, in step S1105, the accumulated information generation unit 111 generates divided area accumulated information of the line segment area 1004 adjacent to the right end of the processing window, and divided area accumulated information of the line segment area 1003. Is stored in the buffer area that had been stored. Since the line segment area 1004 corresponds to the left end of the segment area, the segment area accumulation information of the line segment area 1004 can be easily calculated. That is, cumulative addition may be performed in order from the uppermost pixel of the line segment region 1004. In addition, the segment area cumulative information of the line segment area to the right of the line segment area 1004 is obtained by adding the cumulative addition value sequentially from the uppermost pixel of the right line segment area and the segment area cumulative information of the line segment area 1004. Can be calculated. That is, the calculation can be performed by performing an operation such as replacing the x axis and the y axis in the addition (accumulation information calculation) shown in equations 3 and 4.

  When the next line segment accumulation information is generated and the processing window is shifted to the right by one pixel, the accumulation information generation unit 111 performs the calculation processing of the sum in the specific area in step S1103 for the area. Thereafter, the same processing is repeated until it is determined in step S1104 that the processing window has reached the right end.

  As described above, when the divided area accumulated information held in the block buffer is moved from the position of the area 1001 to the position of the area 1002 by the processing in steps S1101 to S1105, the divided area accumulated information of the vertical line segment area 1003 is changed. The stored area is discarded. In this area, the divided area accumulation information of the vertical line segment area 1004 is held. Such processing is sequentially repeated until the processing window reaches the right end.

  When the processing up to the right end position is completed, in step S1106, the cumulative information generation unit 111 determines whether the last line position of all input information has been processed.

  If the current processing block position has not reached the final line position, in step S1107, the cumulative information generation unit 111 resets the processing window position to the left end one line below. At that time, the origin for calculating the divided region accumulated information is shifted from the origin 1005 to the origin 1006 one line below.

  In step S1102, the cumulative information generation unit 111 uses the origin for calculating the newly set divided area accumulated information in the newly set processing window, and the divided area of the block including the current origin at the upper left. Generate and store cumulative information.

  Next, the cumulative information generation unit 111 repeats the specific area total calculation processing for each block in step S1103. Thereafter, the process is repeated in order until the final line is reached in step S1106, and the entire input information is processed.

  As described above, in steps S1106 to S1107, the processing window is shifted downward by one line with the processing window reaching the right end as a trigger, and the processes in steps S1102 to S1105 are repeated from the left end 1007. At this time, the origin for calculating the divided region accumulated information is a new origin 1006. That is, when the processing window is shifted down by one line, the origin for calculating the divided region accumulated information is also shifted down by one.

  If it is determined in step S1160 that the final line has been reached, the process is completed.

  As described above, in this embodiment, the area 1001 is an area of accumulated divided area information currently held in the block buffer, and the accumulated information holding memory 113-1 has a divided area of the size of the area 1001 at a time. Stores only cumulative information. Also, the cumulative information area 1001 currently held in the block buffer matches the current processing window position. FIG. 10 shows that the divided area accumulated information at the start position (upper left corner) is stored. An area 1002 indicates an area in which the processing window is shifted to the right by one pixel. When this area is processed, the divided area accumulation information of the same area is held in the block buffer.

  In this embodiment, the size of the accumulated information holding memory 113-1 only needs to be the size of the block buffer described above. For example, if the buffer capacity in this embodiment is calculated under the same conditions as in the examples described in the first and second embodiments, the size that needs to be held at one time is one block, so it should be prepared as a minimum The size (depth) of the accumulated information holding memory can be 64 × 64. The width of the accumulated information holding memory is 20 and the same.

  In the present embodiment, the size of the processing window and the size of the divided area are the same, and when the processing window is shifted down by one line, the origin for calculating the divided area accumulated information is also shifted downward. Therefore, the horizontal region division does not substantially occur.

  However, the implementation using the block buffer according to the present embodiment tends to cause an overhead in calculating the divided region accumulated information. That is, it is necessary to calculate the divided region accumulated information corresponding to the pixel at a certain position of the processing target information a plurality of times. On the other hand, in the first and second embodiments, it is only necessary to calculate the divided region accumulated information corresponding to the pixel at a certain position in the processing target information.

(Fourth embodiment)
Next, a fourth embodiment of the present invention will be described. The first to third embodiments relate to a process of calculating divided region accumulated information for two-dimensional processing target information and obtaining the sum of element values of a two-dimensional specific region using the divided region accumulated information. Is. The fourth embodiment relates to processing of processing target information having three or more dimensions.

  The accumulated information can be generated not only for two-dimensional array information but also for multi-dimensional array information of three or more dimensions. FIG. 11 is a diagram illustrating a state of accumulated information in a three-dimensional case. The input information of the three-dimensional array is, for example, moving image information, and becomes a three-dimensional information by adding a one-dimensional time axis to a two-dimensional image.

In FIG. 11A, the element value of the element at the position of the point X in the three-dimensional cumulative information array is the total value of the elements included in the rectangular parallelepiped having the origin and the point X in the input three-dimensional information as a diagonal. . Using such three-dimensional accumulated information, for example, it is possible to obtain the total value of the elements in the rectangular parallelepiped 1201 in FIG. Here, the coordinates of two points indicating the diagonal of the rectangular parallelepiped 1201 are (x ₀ , y ₀ , t ₀ ) and (x ₁ , y ₁ , t ₁ ). Also, assuming that the accumulated information values for each vertex of the rectangular parallelepiped are A, B, C, D, E, F, G, and H, these are the accumulated information values of the coordinates shown in Table 1.

When such a definition is performed, the sum S _{3d of the} elements in the rectangular parallelepiped 1201 of the input information is
S _3d = H−D−F + B− (G−C−E + A)
It is expressed as

  By replacing the two-dimensional divided region accumulated information of the first to third embodiments with the three-dimensional divided region accumulated information for such three-dimensional accumulated information, the accumulated information can be created by the same processing. it can. In this case, the divided area is three-dimensional. For example, with respect to the three-dimensional cumulative information of FIG. 11, the three-dimensional divided region cumulative information is as shown in FIG. In FIG. 12, since the figure becomes complicated, only one divided region 1301 is shown, but the divided region 1301 is divided into the processing target information, and three-dimensional accumulated information is calculated in the divided region. do it.

  Further, the accumulated information for multidimensional input information exceeding three dimensions can be similarly processed if considered in the super rectangular parallelepiped region.

  The embodiment of the present invention can be realized by, for example, a computer executing a program. Also, means for supplying a program to a computer, for example, a computer-readable recording medium such as a CD-ROM recording such a program, or a transmission medium such as the Internet for transmitting such a program is also applied as an embodiment of the present invention. Can do. The above program can also be applied as an embodiment of the present invention. The above program, recording medium, transmission medium, and program product are included in the scope of the present invention.

  That is, the present invention can be applied not only to hardware circuits but also to software processing. For example, in the case of conventional cumulative information, if a 32-bit long type array must be used, but 16 bits can be obtained by using the divided region cumulative information of the present invention, a 16-bit short type array is used. It becomes possible. That is, the buffer capacity to be used can be reduced by half.

  In the above-described embodiment, the band buffer or the block buffer is used as the ring buffer, but the present invention is not limited to such a method of using the memory. For example, a memory address table corresponding to a ring counter may be provided, and processing may be performed while allocating discontinuous areas in predetermined processing units by referring to the table. That is, the ring buffer described in the present invention is not limited to a narrowly defined ring buffer or circular buffer.

  Further, the information processing using the divided region accumulated information is not limited to the pattern recognition process. The present invention is applicable to processing in other fields such as computer graphics as described in the prior art as long as the processing uses accumulated information.

It is a block diagram which shows the structure of the information processing apparatus which concerns on the 1st Embodiment of this invention. 4 is a block diagram illustrating a configuration of a cumulative information generation unit 111 and a connection relationship with a bus I / F 110 and a cumulative information holding unit 113. FIG. 3 is a block diagram illustrating a configuration of an accumulated information use calculation unit 112 and a connection relationship with a bus I / F 110 and an accumulated information holding unit 113. FIG. It is a flowchart which shows operation | movement of the information processing apparatus which concerns on 1st Embodiment. It is a figure which shows an example of a specific area | region. It is a figure which shows a face detection process. It is a flowchart which shows operation | movement (operation | movement at the time of hold | maintaining division area accumulation information with a band buffer) of the information processing apparatus which concerns on 2nd Embodiment. In 2nd Embodiment, it is a figure which shows the mode of the band buffer hold | maintained at once with respect to the whole division area accumulation information. It is a flowchart which shows operation | movement (operation | movement at the time of hold | maintaining division area accumulation information with a block buffer) of the information processing apparatus which concerns on 3rd Embodiment. It is a figure which shows the mode of the block buffer hold | maintained at once with respect to the divisional area cumulative information whole area in 3rd Embodiment. It is a figure which shows the mode of the accumulation information in the case of three dimensions. It is a figure which shows three-dimensional division area accumulation information. It is a figure which shows the example of accumulation information.

Explanation of symbols

100: Cumulative information calculation processing unit 101: CPU
102: Information input unit 103: DMA controller 104: Processing target information storage memory 105: Bus 110: Bus interface unit 111: Cumulative information generation unit 112: Cumulative information use calculation unit 113: Cumulative information holding unit 113-1: Cumulative information Holding memory 113-2: Memory controller 114: Division control unit 201: Input information size storage register 202: Address counter 203: Input element value holding register 204: Horizontal direction accumulated value holding register 205: Previous line accumulated information value reference register 206: Cumulative addition processing units 206-1, 206-2: Adder 207: Initialization control unit 301: Specific area designation register 302: Reference address calculation unit 303: Temporary reference value holding register 304: Addition / subtraction processing unit 305: Calculation result holding register 306: Specific area division

Claims (11)

A dividing means for dividing the processing target information of the multi-dimensional array into a plurality of divided regions;
As the accumulated information value corresponding to each element position in the processing target information, all the information in the area diagonally with the predetermined origin position of the divided area and each element position of the processing target information belonging to the divided area A calculation means for calculating a total value of element values for each of the divided regions;
An information processing apparatus comprising:   The sum total calculating means for obtaining a sum total of element values in a specific area defined on the processing target information using an accumulated information value calculated for each of the divided areas. Information processing device. The sum total calculating means includes:
Determining means for determining whether or not the specific region extends over a plurality of the divided regions;
A specific area dividing means for dividing the specific area into divided specific areas according to each of the divided divided areas when straddling;
Second calculation means for obtaining a sum of element values in the divided specific area for each divided specific area;
The information processing apparatus according to claim 2, further comprising:   The information processing apparatus according to claim 1, wherein sizes of the plurality of divided regions are equal to each other.   5. The information processing apparatus according to claim 2, wherein a size of the plurality of divided regions is equal to or greater than a size of a maximum of the specific regions. The multi-dimensional array is a two-dimensional array;
6. The information processing apparatus according to claim 1, wherein a region whose diagonal is a predetermined origin position of the divided region and each element position of the divided region is a rectangular region.   The information processing apparatus according to claim 2, wherein the specific area is a rectangular area. The multi-dimensional array is an array of three or more dimensions;
The information processing apparatus according to any one of claims 1 to 5, wherein a region whose diagonal is a predetermined origin position of the divided region and each element position of the divided region is a super rectangular parallelepiped. .   The information processing apparatus according to claim 2, 3, 4, 5, or 8, wherein the specific area is a hypercubic area. A division step of dividing the processing target information of the multi-dimensional array into a plurality of divided regions;
As the accumulated information value corresponding to each element position in the processing target information, all the information in the area diagonally with the predetermined origin position of the divided area and each element position of the processing target information belonging to the divided area A calculation step of calculating a total value of element values for each of the divided regions;
An information processing method characterized by comprising: On the computer,
A division step of dividing the processing target information of the multi-dimensional array into a plurality of divided regions;
As the accumulated information value corresponding to each element position in the processing target information, all the information in the area diagonally with the predetermined origin position of the divided area and each element position of the processing target information belonging to the divided area A calculation step of calculating a total value of element values for each of the divided regions;
A program characterized by having executed.

Images