Unfolded convolution for fast feature extraction

• US 7,634,137 B2
• Filed: 10/14/2005
• Issued: 12/15/2009
• Est. Priority Date: 10/14/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chellapilla, Kumar H., Simard, Patrice Y., Steinkraus, David W.
• Primary Examiner(s): Ahmed; Samir A.
• Assistant Examiner(s): Woldemariam; Aklilu k
• Application Number:
  US11/250,819
• Publication Number:
  US 20070086655A1
• Time in Patent Office: 1,523 Days
• Field of Search: 382/190, 382/279, 382/132, 382/128
• US Class Current: 382/190
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18057 Integrating the filters into a hierarchical structure, e.g. convolutional neural networks [CNN]

Abstract

Systems and methods are described that facilitate performing feature extraction across multiple received input features to reduce computational overhead associated with feature processing related to, for instance, optical character recognition. Input feature information can be unfolded and concatenated to generate an aggregated input matrix, which can be convolved with a kernel matrix to produce output feature information for multiple output features concurrently.

Claims

1. A computer-implemented method for extracting features, comprising:

one or more processors implementing instructions stored in one or more processor-accessible storage medium for;

receiving a plurality of input features, I_f, from an input signal, the input features having a height, I_y, and a width, I_x;

unfolding the input features to generate linearized weights, the linearized weights having a height, K_y, and a width, K_x;

determining a horizontal subsampling location, S_x, and a vertical subsampling location, S_y;

concatenating the input features into an input matrix via a processor controllable convolution component, wherein a horizontal component of the input matrix comprises the product of K_x*K_y*I_f, and a vertical component of the input matrix comprises the product of [((I_x−

K_x+1)+(S_x−

1))/S_x]*[(I_y−

K_y+1)+(S_y−

1))/S_y]; and

multiplying the input matrix by a kernel matrix to generate a matrix product.

2. The method of claim 1, further comprising:

computing a gradients of the error of the unfolded matrix with respect to a weight; and

computing a gradients of the error of the unfolded matrix with respect to the input features.

3. The method of claim 1, wherein unfolding the input features including unfolding at least one element from each input feature into each column.

4. The method of claim 1, further comprising rewriting the input matrix so that at least one row of the input matrix comprises at least one feature required to compute one output feature.

5. The method of claim 4, rewriting the input matrix further comprises duplicating the input features in the input matrix.

6. The method of claim 1, generating the input matrix further comprises subsampling the input features.

7. The method of claim 1, at least one column in the kernel matrix represents at least one output feature.

8. The method of claim 1, further comprising generating a plurality of reduced input matrices by subsampling the unfolded input.

9. The method of claim 8, further comprising reorganizing the output features into a two-dimensional matrix consistent with an original two-dimensional layout of the input features and performing a character recognition protocol.

10. A computer-implemented system that employs a convolutional neural network to facilitate feature extraction for optical character recognition, comprising:

a processor; and

a memory into which a plurality of computer-executable instructions are loaded, the plurality of instructions performing a method comprising;

receiving a plurality of input features from an input signal, the input features having a height, I_y, and a width, I_x, wherein I_f is the number of received input features;

weighting the input features to generate linearized weights, the linearized weights gleaned from the input features, the linearized weights having a height, K_y, and a width, K_x;

unfolding multiple input features;

concatenating the unfolded input features to generate an input feature matrix, wherein a horizontal component of the input matrix comprises the product K_x*K_y*I_f, and wherein a vertical component of the input feature matrix comprises the product of [((I_x−

K_x+1)+(S_x−

1))/S_x]*[(I_y−

K_y+1)+(S_y−

1))/S_y], where S_x is a horizontal subsampling location and S_y is a vertical subsampling location;

generating a kernel matrix; and

computing a matrix of output features by generating a matrix product of the input feature matrix and the kernel matrix.

11. The system of claim 10, further comprising performing character recognition based at least in part on information associated with the matrix product.

12. The system of claim 10, further comprising generating multiple output features based at least in part on the matrix product.

13. The system of claim 10, wherein the processor further analyzes the matrix of out features to perform character recognition.