INFORMATION PROCESSING METHOD AND APPARATUS

• US 20110058741A1
• Filed: 08/31/2010
• Published: 03/10/2011
• Est. Priority Date: 09/07/2009
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Ito, Yoshinori, Yamamoto, Takahisa, Kato, Masami
• Granted Patent: US 9,014,483 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06F 18/2148 characterised by the process organisation or structure, e.g. boosting cascade
• CPC Class Codes: G06V 10/446 using Haar-like filters, e.g. using integral image techniques
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/7747 Organisation of the process, e.g. bagging or boosting
• CPC Class Codes: G06V 10/94 Hardware or software architectures specially adapted for image or video understanding

Abstract

Input information of a multidimensional array is divided into a plurality of divided areas, accumulated information is generated by calculating accumulated values at respective element positions of the input information from a corresponding reference location for each of the plurality of divided areas, and the generated accumulated information is held in a memory for each divided area. Calculation using the accumulated information is executed for a predetermined processing range. The input information is divided into the plurality of divided areas so that two neighboring divided areas have an overlapping area, and the overlapping area has a size at least in which the whole processing range fits.

Claims

1. An information processing method comprising:

a dividing step of dividing input information of a multidimensional array into a plurality of divided areas;

a generating step of generating accumulated information by calculating accumulated values at respective element positions of the input information from a corresponding reference location for each of the plurality of divided areas;

a holding step of holding the accumulated information generated in the generating step in a memory; and

a calculating step of executing calculation using the accumulated information for a predetermined processing range,

wherein in the dividing step, the input information is divided into the plurality of divided areas so that two neighboring divided areas have an overlapping area, and the overlapping area has a size at least in which the whole processing range fits.

2. The method according to claim 1, wherein in the calculating step, all accumulated values used for one processing range are obtained from accumulated information generated in correspondence with one divided area.

3. The method according to claim 1, wherein a storage size of the accumulated information assured in the memory is determined based on a bit precision of each element of the input information and a size of each divided area.

4. The method according to claim 1, wherein in the dividing step, division is not performed in at least one direction of dimension of a plurality of dimensions of the input information.

5. The method according to claim 4, wherein in the generating step, a reference location is set to generate accumulated information for each part included in a partial area, which has a length of the divided area in a direction of dimension in which the division is performed in the dividing step and a predetermined length in a direction of dimension in which the division is not performed in the dividing step, of the plurality of divided areas, and

in the holding step, accumulated information of the partial area is held.

6. The method according to claim 1, wherein in the generating step, accumulated information of a part included in a partial area, which has a full length of the input information in a direction of dimension in which division is performed in the dividing step and a predetermined length in a direction of dimension in which the division is not performed in the dividing step, of the plurality of divided areas is generated in turn in synchronism with calculation in the calculating step, and

in the holding step, accumulated information of the partial area is held.

7. The method according to claim 6, wherein in the generating step, every time calculation in the calculating step for the partial area ends, the partial area is shifted in the direction of dimension in which the division is not performed, and accumulated information in the shifted partial area is generated by additionally calculating accumulated values for elements of the input information, which newly enter the shifted partial area.

8. The method according to claim 7, wherein in the holding step, pieces of accumulated information obtained for two neighboring partial areas are respectively held in a first buffer and a second buffer, and

in the generating step, pieces of accumulated information respectively corresponding to the two neighboring partial areas are generated in an overlapping area configured by the two neighboring partial areas, and are held in the first buffer and the second buffer.

9. The method according to claim 7, wherein in the calculating step, predetermined calculation is repeated while shifting the processing range in the direction of dimension in which the division is performed, and

in the generating step, for elements of the input information which newly enter the shifted processing range every time the processing range is shifted, accumulated values of the elements in a partial area to which the elements belong are calculated.

10. The method according to claim 9, wherein the predetermined length of the partial area is equal to a length of the processing range in a corresponding direction of dimension, the length of the partial area in the direction of dimension in which the division is performed in the dividing step is twice the length of the processing range in the corresponding direction of dimension, and the overlapping area has a size equal to the processing range, and

in the generating step, when the processing range is shifted in the direction of dimension in which the division is performed, accumulated values of elements of the input information, which newly enter the shifted processing range are additionally generated.

11. The method according to claim 7, wherein in the holding step, when an area for holding the accumulated values is full and additionally calculated accumulated information is to be stored, oldest accumulated information for an amount of the additionally calculated accumulated information is discarded, and the additionally calculated accumulated information is held in that area.

12. The method according to claim 6, wherein a storage size of the accumulated information assured in the memory is determined based on a bit precision of the element and a size of the partial area.

13. The method according to claim 1, wherein the input information is information of a two-dimensional array, and a sum total value of all elements of the input information, which correspond to an interior of a rectangular area having a reference location of each divided area and each element position of the divided area as diagonal points is calculated as an accumulated value corresponding to that element position of the divided area.

14. The method according to claim 1, wherein the input information is information of a multidimensional array of not less than three dimensions, and a sum total value of all elements of the input information, which correspond to an interior of an area of a hyper-rectangular parallelepiped having a reference location of each divided area and each element position of the divided area as diagonal points is calculated as an accumulated value corresponding to that element position of the divided area.

16. A computer-readable storage medium storing a program for controlling a computer to execute respective steps of an information processing method according to claim 1.

15. An information processing apparatus comprising:

a dividing unit configured to divide input information of a multidimensional array into a plurality of divided areas;

a generating unit configured to generate accumulated information by calculating accumulated values at respective element positions of the input information from a corresponding reference location for each of the plurality of divided areas;

a holding unit configured to hold the accumulated information generated by the generating unit in a memory for each divided area; and

a calculating unit configured to execute calculation using the accumulated information for a predetermined processing range,

wherein the dividing unit divides the input information into the plurality of divided areas so that two neighboring divided areas have an overlapping area, and the overlapping area has a size at least in which the whole processing range fits.