Method for accelerating a CDVS extraction process based on a GPGPU platform

• US 10,643,299 B2
• Filed: 12/05/2016
• Issued: 05/05/2020
• Est. Priority Date: 06/28/2016
• Status: Active Grant

• Current Assignee: Peking University Shenzhen Graduate School
• Original Assignee: Peking University Shenzhen Graduate School
• Inventors: Wang, Ronggang, Zhang, Shen, Wang, Zhenyu, Gao, Wen
• Primary Examiner(s): Mazumder, Tapas
• Application Number:
  US16/307,329
• Publication Number:
  US 20190139186A1
• Time in Patent Office: 1,247 Days
• Field of Search: None
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 9/3877 using a slave processor, e.g. coprocessor peripheral processor G06F13/12; vector processor G06F15/8053
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06V 10/454 Integrating the filters into a hierarchical structure, e.g. convolutional neural networks [CNN]

Abstract

Embodiments of the present disclosure provide a method for accelerating CDVS extraction process based on a GPGPU platform, wherein for the stages of feature detection and local descriptor computation of the CDVS extraction process, operation logics and parallelism strategies of respective inter-pixel parallelism sub-procedures and respective inter-feature point parallelism sub-procedures are implemented by leveraging an OpenCL general-purpose parallelism programming framework, and acceleration is achieved by leveraging a GPU'"'"'s parallelism computation capability; including: partitioning computing tasks for a GPU and a CPU; reconstructing an image scale pyramid storage model; assigning parallelism strategies to respective sub-procedures for the GPU; and applying local memory to mitigate the access bottleneck. The technical solution of the present disclosure may accelerate the CDVS extraction process and significantly enhances the extraction performance.

Claims

1. A method for accelerating a Compact Descriptors for Visual Search (CDVS) extraction process based on a General-Purpose Computing on Graphics Processing Units (GPGPU) platform, comprising successive steps of:

Step 1;

partitioning Central Processing Unit (CPU) computing tasks and Graphics Processing Units (GPU) computing tasks by assigning a feature detection stage and a local descriptor computation stage in a CDVS extraction process to a GPU and assigning a feature selection stage, a global descriptor aggregation stage, a local descriptor compression stage, and a coordinate coding stage left in the CDVS extraction process to a CPU;

wherein the feature detection stage includes sub-procedures including a Gaussian convolution sub-procedure, a Laplacian convolution sub-procedure, a polynomial coefficient computation sub-procedure, a response value computation sub-procedure, and a detection sub-procedure;

wherein the local descriptor computation stage include sub-procedures including a gradient computation sub-procedure, a primary orientation assignment sub-procedure, and a descriptor computation sub-procedure; and

obtaining source kernel programs for operation logics of the sub-procedures assigned to the GPU to further obtain GPU executable program objects;

Step 2;

reconstructing an image scale-space pyramid storage model to transform an inter-octave discontinuous storage model into an inter-octave continuous storage model, so as to first complete inter-pixel parallelizable procedures or sub-procedures at all octaves of a pyramid and then uniformly compute inter-feature point parallelizable sub-procedures;

wherein the inter-pixel parallelizable procedures or sub-procedures include the feature detection stage and the gradient computation sub-procedure of the local descriptor computation stage; and

wherein the inter-feature point parallelizable sub-procedures include the primary orientation assignment sub-procedure and the descriptor computation sub-procedure of the local descriptor computation stage;

Step 3;

specifying parallelism strategies for the respective sub-procedures assigned to the GPU using a two-dimensional work-group partition and a one-dimensional work-group partition, respectively;

wherein the respective sub-procedures assigned to the GPU include the the Gaussian convolution sub-procedure, the Laplacian convolution sub-procedure, the polynomial coefficient computation sub-procedure, the response value computation sub-procedure, and the detection sub-procedure of the feature detection stage and the gradient computation sub-procedure, the primary orientation assignment sub-procedure, and the descriptor computation sub-procedure of the local descriptor computation stage;

Step 4;

applying local memory, wherein during the descriptor computation sub-procedure of the local descriptor computation stage, feature points in a one-dimensional work-group of a present sub-procedure are assigned a storage space in the local memory, such that during the descriptor computation sub-procedure, all updates occur in the assigned storage space in the local memory; and

updating a global memory using descriptor data in the local memory after completing the descriptor computation sub-procedure; and

thereby realizing acceleration of the CDVS extraction process.

2. The method for accelerating a CDVS extraction process based on the GPGPU platform according to claim 1, wherein the first step of partitioning CPU computing tasks and GPU computing tasks are further implemented through the following operations:

11) implementing, by leveraging an OpenCL kernel program, operation logics of the Gaussian convolution sub-procedure, the Laplacian convolution sub-procedure, the polynomial coefficient computation sub-procedure, the response value computation sub-procedure, the detection sub-procedure, the gradient computation sub-procedure, the primary orientation assignment sub-procedure, and the descriptor computation sub-procedure, to obtain eight source kernel programs;

12) successively invoking OpenCL interfaces clCreateProgramWithSource, clBuildProgram, and clCreateKernel to soft compile the eight source kernel programs in step

     11) to obtain GPU executable program objects; and

13) implementing, by leveraging C language, operation logics of the feature selection stage, the local descriptor compression stage, the coordinate coding stage, and the global descriptor aggregation stage.

3. The method for accelerating a CDVS extraction process based on the GPGPU platform according to claim 1, wherein the second step of reconstructing the image scale-space pyramid storage model, are further implemented through the following operations:

21) invoking OpenCL interface clCreateBuffer to uniformly apply for a storage space on the GPU for all octaves of the image scale-space pyramid;

wherein, assuming that the length and width of an input image are W and H, respectively, and the pyramid include N (N=1, 2, 3 . . . ) octaves, a storage space size S is computed through Equation 1;

4. The method for accelerating a CDVS extraction process based on the GPGPU platform according to claim 1, wherein the third step of specifying parallelism strategies for the respective sub-procedures assigned to the GPU using the two-dimensional work-group partition and the one-dimensional work-group partition, respectively, comprises steps of:

31) specifying a global work-group size for all inter-pixel parallelizable sub-procedures;

32) specifying a local work-group size for all inter-pixel parallelizable sub-procedures;

33) specifying a global work-group size for all inter-feature point parallelizable sub-procedures; and

34) specifying a local work-group size for all inter-feature point parallelizable sub-procedures.

5. The method for accelerating a CDVS extraction process based on the GPGPU platform according to claim 4, wherein the global work-group size in step 31) is specified by assuming that the length and width of an octave of the pyramid are w and h, respectively, and then setting an array globalWorkSize[2] that including two integers, causing globalWorkSize[0]=w, globalWorkSize[1]=h;

the local work-group size in step

     32) is specified by directly setting an array localWorkSize[2] including two integers, causing that when the size of an octave of the pyramid is 640×

480p, then localWorkSize[0]=32 and localWorkSize[1]=32;

when the size of an octave of the pyramid is 320×

240p, then localWorkSize[0]=32 and localWorkSize[1]=16;

when the size of an octave of the pyramid is 160×

120p, then localWorkSize[0]=32 and localWorkSize[1]=8;

when the size of an octave of the pyramid is 80×

60p, when localWorkSize[0]=16 and localWorkSize[1]=4;

when the size of an octave of the pyramid is 40×

30p, then localWorkSize[0]=8 and localWorkSize[1]=2;

the global work-group size in step

     33) is specified by assuming that a total amount of the feature points detected at the feature detection stage is n(n=1, 2, 3, . . . ), and setting an array globalWorkSize[1] including one integer, causing globalWorkSize[0]=n; and

the local work-group size in step

     34) is specified by directly setting an array localWorkSize[1] including one integer, causing localWorkSize[0]=32.

6. The method for accelerating a CDVS extraction process based on the GPGPU platform according to claim 5, wherein a parallelism execution strategy of the GPU is determined by specifying the set globalWorkSize and localWorkSize as parameters of OpenCL interface clEnqueueNDRangeKernel, and in partitioning a local work-group, 32 is an optimal individual dimension partition of a work-group size.

7. The method for accelerating a CDVS extraction process based on the GPGPU platform according to claim 1, wherein in the third step, a two-dimensional work-group is assigned to respective sub-procedures with pixels as independent operands;

and a one-dimensional work-group is assigned to respective sub-procedures with feature points as independent operands.

8. The method for accelerating a CDVS extraction process based on the GPGPU platform according to claim 1, wherein the applying local memory in step 4 comprises the following operations:

41) assigning local memory to the feature points in the one-dimensional work-group;

42) during executing the kernel program, accessing to and updating of descriptors whose feature points include 128 floating points occur over the local memory assigned at step

     41); and

43) updating the descriptors in the global memory using the descriptors in the assigned local memory after completing the operation logics of the sub-procedures assigned to the GPU.

9. The method for accelerating a CDVS extraction process based on the GPGPU platform according to claim 1, wherein an input image in the extracting process is a 640×

480p JPEG image.