Method for producing a histogram of oriented gradients
View Patent ↗A method for producing a histogram of oriented gradients (HOG) for at least a portion of an image comprises dividing said image portion into cells, each cell comprising a plurality of image pixels. For each image pixel of a cell, a horizontal gradient component, gx, and a vertical gradient component, gy, is obtained based on differences in pixel values along at least a row of said image and a column of said image respectively including the pixel. A gradient is allocated to one of a plurality of sectors, each sector extending through a range of orientation angles. At least some of said sectors are divided from adjacent sectors along lines including gx=2 n ·gy, where n is any integer value with a magnitude greater than or equal to 1. At least one sector is associated with a bin; and a count of each instance of a pixel gradient of a cell associated with a bin is performed to provide a HOG for said cell.
1. A method for producing a histogram of oriented gradients (HOG) for at least a portion of an image comprising:
dividing said image portion into cells, each cell comprising a plurality of image pixels;
for each image pixel of a cell,
obtaining a horizontal gradient component, gx, and a vertical gradient component, gy, based on differences in pixel values along at least a row of said image and a column of said image respectively including said pixel; and
allocating a gradient to one of a plurality of sectors, each sector extending through a range of orientation angles and at least some of said sectors being divided from adjacent sectors along lines including gx=2 n ·gy, where n is any integer value with a magnitude greater than or equal to 1, said allocating a gradient to a sector being divided from an adjacent sector along a line including gx=2 n ·gy using only shift and comparison logic;
associating at least one sector with a bin; and
accumulating each instance of a pixel gradient of a cell associated with a bin to provide a HOG for said cell.
2. A method according to claim 1 further comprising, for each image pixel of a cell, calculating a magnitude of said gradient.
3. A method according to claim 2 comprising said calculating said magnitude according to the formula:
mag=|gx|+|gy |−min(| gx|,|gy |)/2.
4. A method according to claim 1 wherein said sectors are divided from adjacent sectors along the following lines: gx=0; gx=4*gy; gx=2*gy; gx=gy; gy=2*gx; gy=4*gx; and gy=0.
5. A method according to claim 1 wherein each cell comprises 4×4 image pixels.
6. A method according to claim 1 wherein each cell is displaced by steps of one of 1, 2 or 4 pixels vertically or horizontally from an adjacent cell.
7. A method according to claim 1 wherein said obtaining a gradient component comprises subtracting a pixel value for a first pixel immediately adjacent a pixel from a pixel value for a second pixel immediately adjacent said pixel and opposite said first pixel.
8. A method according to claim 1 comprising associating at least one bin with a plurality of sectors.
9. A method according to claim 8 wherein said sectors are either adjacent or non-adjacent.
10. A method according to claim 8 wherein a plurality of bins are associated with a given sector.
11. A method according to claim 8 wherein not all sectors are associated with a bin.
12. A method according to claim 1 comprising associating each sector with a respective bin.
13. A method according to claim 1 wherein said pixel values are intensity values.
14. A method according to claim 1 wherein said pixel values are colour values.
15. A method according to claim 1 further comprising the step of combining respective HOGs for a plurality of adjacent cells.
16. A method according to claim 1 further comprising:
calculating a magnitude m(x, y) for each pixel gradient according to the formula:
m
(
x
,
y
)
=
K
*
gx
(
x
,
y
)
c
where K comprises a look-up table of integer value approximations for cos(∝) indexed using an allocated sector index, where cos(∝) is an angle corresponding to each sector index and where c is a constant and a power of 2.
17. An image processing system including digital logic for implementing the method of claim 1 .
18. An image processing system according to claim 17 wherein said logic includes a plurality of line buffers and wherein said logic is arranged to receive an image pixel-by-pixel on each cycle of a clock and to accumulate previous pixel values in said line buffers.
19. An image processing system according to claim 18 wherein said logic is arranged to produce said horizontal and vertical gradient components for one or more pixels stored in said line buffers in the same column of an image as a currently received pixel.
20. An image processing system according to claim 19 wherein said logic includes a buffer arranged to accumulate indicators for which bins each pixel of a cell is associated with.
21. An image processing system according to claim 20 wherein said logic comprises a counter connected to said buffer for providing said count of pixel gradients of a cell associated with respective bins.
22. An image processing system according to claim 21 wherein said logic is arranged to provide said count synchronously in multiple steps of said clock cycle.
23. An image processing system according to claim 17 including logic for combining tests for whether a gradient for a pixel lies within the boundaries of any of said sectors.
24. An image processing system according to claim 23 wherein said tests comprise:
gx> 0; gy> 0; | gx|>|gy|; |gx|> 2| gy | OR | gy|> 2| gx |; and | gx |>4| gy | OR | gy |>4| gx|.
25. An image processing system according to claim 23 wherein said logic for combining tests is replicated for each sector.
26. An image processing system according to claim 23 including logic for combining said test results with respective bin configurations, each bin configuration associating a bin with a combination of said sectors, to provide a bin mask indicating any configured bins in which said gradient lies.
27. An image processing system including digital logic for producing a histogram of oriented gradients (HOG) for respective cells from at least a portion of an image, each cell comprising a plurality of image pixels,
said logic including a plurality of line buffers and being arranged to receive an image pixel-by-pixel on each cycle of a clock and to accumulate previous pixel values in said line buffers,
said logic being arranged to produce a horizontal gradient component, gx, and a vertical gradient component, gy, for one or more pixels stored in said line buffers from the same column of an image as a currently received pixel based on differences in pixel values along at least a row of said image and a column of said image respectively including said one or more pixels,
said logic being arranged to allocate respective gradients for said one or more pixels to one of a plurality of bins, each bin extending through a range of orientation angles, said logic including a buffer arranged to accumulate indicators for which bins each pixel of a cell is associated with, and
said logic including a counter connected to said buffer for providing a count of pixel gradients of a cell associated with respective bins, said logic being arranged to provide said count synchronously in multiple steps of said clock cycle according to cell displacement.
28. An image processing system according to claim 27 wherein said logic for allocating respective gradients includes logic for testing if:
gx> 0; gy> 0; | gx|>|gy|; |gx|> 2| gy | OR | gy|> 2| gx |; and | gx|> 4| gy | OR | gy|> 4| gx|.
29. A method for producing a histogram of oriented gradients (HOG) for at least a portion of an image comprising:
dividing said image portion into cells, each cell comprising a plurality of image pixels;
for each image pixel of a cell,
obtaining a horizontal gradient component, gx, and a vertical gradient component, gy, based on differences in pixel values along at least a row of said image and a column of said image respectively including said pixel; and
allocating a gradient to one of a plurality of sectors, where n is a sector index, each sector extending through a range of orientation angles and at least some of said sectors being divided from adjacent sectors according to the inequalities: b*16<a*(n+1) where 0≤n≤5, b=gy and a=gx; and b*16<a*(13−n) where 7≤n≤12, a=gx+gy and b=gx−gy;
associating at least one sector with a bin; and
accumulating each instance of a pixel gradient of a cell associated with a bin to provide a HOG for said cell.
30. A method according to claim 29 comprising: prior to allocating a pixel gradient to one of a plurality of sectors:
reversing the horizontal gradient component, gx of a pixel if the horizontal gradient component is less than 0;
reversing the vertical gradient component, gy of a pixel if the vertical gradient component is less than 0; and
interchanging the horizontal and vertical gradient components of a pixel if the vertical gradient component is greater than the horizontal gradient component in order to map pixel gradients to a common half-quadrant; and
after allocating a pixel gradient to one of a plurality of sectors:
mapping said allocated sector to a sector of a full circle according to said reversing and interchanging.
31. A method according to claim 29 wherein associating a sector with bin comprises using an allocated sector index n as an index for a look up table.
32. A method according to claim 29 further comprising:
calculating a magnitude m(x, y) for each pixel gradient according to the formula:
m
(
x
,
y
)
=
K
*
gx
(
x
,
y
)
c
where K comprises a look-up table of integer value approximations for cos(∝) indexed using an allocated sector index n, where cos(∝) is an angle corresponding to each sector index and where c is a constant and a power of 2.
33. An image processing system including digital logic for implementing the method of claim 29 .
34. A method for producing a histogram of oriented gradients (HOG) for at least a portion of an image comprising:
dividing said image portion into cells, each cell comprising a plurality of image pixels;
associating at least one sector with a bin, each sector corresponding to a respective angle within a full circle,
for each image pixel of a cell,
obtaining a horizontal gradient component, gx, and a vertical gradient component, gy, based on differences in pixel values along at least a row of said image and a column of said image respectively including said pixel; and
allocating a gradient weight to a sector of a pair of sectors bounding said pixel gradient according to a relative angle of said pixel gradient to each of the pair of sectors bounding said pixel gradient; and
allocating the gradient weight for a sector to an associated bin according to an angular relationship between said sector and said associated bin; and
accumulating a weighted pixel gradient for each pixel of a cell associated with a bin to provide a HOG for said cell.
35. A method according to claim 34 wherein said allocating a gradient weight W1 to a sector comprises calculating said gradient weight according to the formula:
W
1
=
a
1
a
1
+
a
2
=
1
-
W
0
where a1 and a2 are the intra-sector angles of the pixel gradient, and where W0 comprises the weight for the other sector of the pair.
36. A method according to claim 35 wherein said angle a1 is approximated with said vertical gradient component gy, and said angle a1+a2 is approximated with a maximum vertical gradient component for a sector.
37. A method according to claim 36 comprising employing a lookup table Kw to approximate said angle a1+a2 as a function of said horizontal gradient component gx and calculating said weights W1, W0 according to the formulae:
W
1
=
gy
(
x
,
y
)
*
Kw
c
=
1
-
W
0
where c is a constant and a power of 2.
38. A method according to claim 34 wherein sectors extend along lines including gx=2 n ·gy, where n is any integer value with a magnitude greater than or equal to 1.
39. A method according to claim 34 , wherein sectors each having an index n extend along lines: b*16=a*(n+1) where 0≤n≤5, b=gy and a=gx; and b*16=a*(13−n) where 7≤n≤12, a=gx+gy and b=gx−gy.
40. An image processing system including digital logic for implementing the method of claim 34 .