# US 12,118,640 B2 · Hardware accelerator for histogram of oriented gradients computation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,118,640 B2
- Document ID: US12118640B2
- Status: Granted
- Kind: B2
- Application number: 17/314,177
- Filed: 2021-05-07
- Published: 2021-08-26
- Granted: 2024-10-15
- Earliest claimed: 2017-04-18
- Assignees: Texas Instruments Incorporated
- Applicants: Texas Instruments Incorporated
- Inventors: Aishwarya Dubey
- Web page: https://patentgrep.com/patent/US12118640B2

## CPC

- G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining
- G06T 7/10: Segmentation; Edge detection (motion-based segmentation G06T7/215)
- G06T 7/13: Edge detection
- G06V 10/44: Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
- G06V 10/473: {using gradient analysis}
- 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
- G06V 10/94: Hardware or software architectures specially adapted for image or video understanding
- G06V 10/955: {using specific electronic processors}
- G06F 2218/08: Feature extraction
- G06T 2200/28: involving image processing hardware
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A hardware accelerator for histogram of oriented gradients computation is provided that includes a gradient computation component configured to compute gradients Gx and Gy of a pixel, a bin identification component configured to determine a bin id of an angular bin for the pixel based on a plurality of representative orientation angles, Gx, and signs of Gx and Gy, and a magnitude component configured to determine a magnitude of the gradients Gmag based on the plurality of representative orientation angles and the bin id.

## Claims

### Claim 1

A device comprising:
a gradient component configured to determine, for a pixel, a first gradient value and a second gradient value;
an estimation component coupled to the gradient component and configured to:
receive the first gradient value; and
for each angle of a set of angles, determine a respective value by multiplying the first gradient value by a tangent of the respective angle;
a comparator coupled to the gradient component and the estimation component and configured to:
receive the second gradient value;
receive the respective values of the set of angles; and
for each of the respective values of the set of angles, compare the respective value to the second gradient value to produce a respective comparison of a set of comparisons;
a bin identification component coupled to the comparator and configured to:
receive the set of comparisons; and
determine a histogram bin for the pixel based on the set of comparisons;
a magnitude component having an input coupled to the gradient component and configured to:
receive the first gradient value at the input of the magnitude component; and
for each angle of the set of angles, determine a respective magnitude value by multiplying the first gradient value by a ratio of lengths of line segments of a right triangle forming the respective angle;
a magnitude selector having first and second inputs respectively coupled to the gradient component and to the bin identification component, the magnitude selector configured to receive at the first input of the magnitude selector an identifier of the histogram bin; and
a multiplexer having first and second inputs respectively coupled to the magnitude component and to the magnitude selector, the multiplexer configured to receive at the first input of the multiplexer the respective magnitude values of the set of angles;
wherein the magnitude selector is further configured to cause the multiplexer to output a first magnitude of the respective magnitude values of the set of angles based on the identifier of the histogram bin.

### Claim 2 (depends on 1)

The device of claim 1, wherein:
the gradient component is further configured to determine a first sign bit of the first gradient value and a second sign bit of the second gradient value; and
the bin identification component is further configured to:
receive the first sign bit and the second sign bit; and
determine the histogram bin associated with the pixel based on the first sign bit and the second sign bit.

### Claim 3 (depends on 2)

The device of claim 2, wherein the bin identification component is further configured to:
determine a quadrant associated with the pixel based on the first sign bit and the second sign bit; and
determine the histogram bin for the pixel based on the set of comparisons and further based on the quadrant.

### Claim 4 (depends on 1)

The device of claim 1, wherein
the ratio of lengths of line segments of a right triangle forming the respective angle is a secant of the respective angle;
the multiplexer is configured to receive, at the second input of the multiplexer, a selector value from the magnitude selector; and
the magnitude selector is configured to receive, at the second input of the magnitude selector, sign bits from the gradient component.

### Claim 5 (depends on 4)

The device of claim 4, further comprising a histogram of gradients generator coupled to the bin identification component and to the multiplexer and configured to determine a histogram of gradients based on the identifier of the histogram bin and the first magnitude.

### Claim 6 (depends on 4)

The device of claim 4, wherein:
the gradient component is further configured to determine a first sign bit of the first gradient value and a second sign bit of the second gradient value, the first sign bit and the second sign bit being at least a subset of the sign bits; and
the magnitude selector is further configured to:
receive, at the second input of the magnitude selector, the first sign bit and the second sign bit; and
cause the multiplexer to provide the first magnitude based on the first sign bit and the second sign bit.

### Claim 7 (depends on 1)

The device of claim 1, wherein the estimation component includes a coordinate rotation digital computer (CORDIC) engine configured to determine, for each angle of the set of angles, the tangent of the respective angle.

### Claim 8 (depends on 1)

The device of claim 1, wherein:
the bin identification component includes a memory configured to store a lookup table; and
the bin identification component is configured to determine the histogram bin by querying the lookup table based on the set of comparisons.

### Claim 9 (depends on 1)

The device of claim 1, wherein each angle of the set of angles is within a quadrant.

### Claim 10 (depends on 1)

The device of claim 1, wherein each angle of the set of angles is between 0° and 90°.

### Claim 11 (depends on 1)

The device of claim 1, wherein the estimation component is configured to determine the respective values for the set of angles in parallel.

### Claim 12

A device comprising:
a gradient component configured to determine, for a pixel, a first gradient value;
a magnitude component coupled to the gradient component and configured to:
receive the first gradient value; and
for each angle of a set of angles, determine a respective magnitude value by multiplying the first gradient value by a secant of the respective angle;
a multiplexer coupled to the magnitude component and configured to receive the respective magnitude values of the set of angles; and
a magnitude selector coupled the multiplexer and configured to:
receive an identifier of a histogram bin for the pixel; and
cause the multiplexer to provide a first magnitude of the respective magnitude values of the set of angles based on the identifier of the histogram bin.

### Claim 13 (depends on 12)

The device of claim 12, wherein:
the gradient component is further configured to determine:
a first sign bit of the first gradient value;
a second gradient value; and
a second sign bit of the second gradient value; and
the magnitude selector is further configured to:
receive the first sign bit and the second sign bit; and
cause the multiplexer to provide the first magnitude based on the first sign bit and the second sign bit.

### Claim 14 (depends on 12)

The device of claim 12, wherein:
the gradient component is further configured to determine a second gradient value; and
the device further comprises:
an estimation component coupled to the gradient component and configured to:
receive the first gradient value; and
for each angle of the set of angles, determine a respective value by multiplying the first gradient value by a tangent of the respective angle;
a comparator coupled to the gradient component and the estimation component and configured to:
receive the second gradient value;
receive the respective values of the set of angles; and
for each of the respective values of the set of angles, compare the respective value to the second gradient value to produce a respective comparison of a set of comparisons; and
a bin identification component coupled to the comparator and configured to:
receive the set of comparisons;
determine the histogram bin for the pixel based on the set of comparisons; and
provide the identifier of the histogram bin to the magnitude selector.

### Claim 15 (depends on 14)

The device of claim 14, wherein:
the gradient component is further configured to determine a first sign bit of the first gradient value and a second sign bit of the second gradient value; and
the bin identification component is further configured to:
receive the first sign bit and the second sign bit; and
determine the histogram bin for the pixel based on the first sign bit and the second sign bit.

### Claim 16 (depends on 15)

The device of claim 15, wherein the bin identification component is further configured to:
determine a quadrant associated with the pixel based on the first sign bit and the second sign bit; and
determine the histogram bin for the pixel based on the set of comparisons and further based on the quadrant.

### Claim 17 (depends on 12)

The device of claim 12, wherein the magnitude component includes a coordinate rotation digital computer (CORDIC) engine configured to determine, for each angle of the set of angles, the secant of the respective angle.

### Claim 18 (depends on 12)

The device of claim 12, wherein each angle of the set of angles is within a quadrant.

### Claim 19 (depends on 12)

The device of claim 12, wherein each angle of the set of angles is between 0° and 90°.

### Claim 20 (depends on 12)

The device of claim 12, wherein the magnitude component is configured to determine the respective magnitude values for the set of angles in parallel.