3

I read similar question in Stack Overflow. I tried, but I still can not understand how it works.

I read OpenCV document cv::HoughCircles, here are some explanation about dp parameter:

Inverse ratio of the accumulator resolution to the image resolution. For example, if dp=1 , the accumulator has the same resolution as the input image. If dp=2 , the accumulator has half as big width and height.

Here are my question. For example, if dp = 1, the size of accumulator is same as image, there is a consistent one-to-one match between pixels in image and positions in accumulator, but if dp = 2, how to match?

Thanks in advance.

Community
  • 1
  • 1
user5746429
  • 135
  • 2
  • 9

1 Answers1

2

There is no such thing as a one-to-one match here. You do have an image with pixels and a hough space, which is used for voting for circles. This parameter is just a convenient way to specify the size of the hough space relatively to the image size.

Please take a look at this answer for more details.

EDIT:

Your image has (x,y)-coordinates. Your circle hough space has (a,b,r)-coordinates, whereas (a,b) are the circle centers and r are the radii. Let's say you find a edge pixel. Now you vote for each circle, which could go through this edge pixel. I found this nice picture of hough space with a single vote i.e. a single edge pixel (continuous case). In practice this vote happens within the 3D accumulator matrix. You can think of it as rasterization of this continuous case.

Now, as already mentioned the dp parameter defines the size of this accumulator matrix relatively to your image size. The bigger the dp parameter the lower the resolution of your rasterization. It's like taking photos with different resolutions. If you downsize your photo multiple pixels will reduce to a single one. Same happens if you reduce your accumulator matrix respectively increase your dp parameter. Multiple votes for different circle centers (which lie next to each other) and radii (which are of similar size) are now merged, i.e. you do get less accurate circle parameters, but a more "robust" voting.

Please be aware that the OpenCV implementation is a little bit more complicated (they use the Hough gradient method instead of the standard Hough transform) but the considerations still apply.

Community
  • 1
  • 1
gfkri
  • 2,151
  • 21
  • 23
  • Thank you for your answer, but I still have questions. Hough space is 3D matrix when it's used for detecting circles. As [wikipedia](https://en.wikipedia.org/wiki/Circle_Hough_Transform) says, we find local maxima in the accumulator matrix. But It's expensive to find local maxima in 3D. So we choose trade-off way that is set the range of radius. That degenerate the dimension of matrix (for voting) to 2D so that we can find local maxima quickly. In your another answer, the smaller your dp, the higher the resolution of your voting. When dp = 1, I know the size of matrix is same as image. – user5746429 Jan 12 '16 at 05:32
  • Then for each “edge” point in the original space, we can formulate a circle in the parameter space and increase the voting number of the grid cell which the circle passing through. Because the size of matrix is same as image, we can find a consistent one-to-one match for voting, then we find local maxima and know its coordinate (x,y,r). In the other word, when the size is same, I know where to vote. But if dp = 2 or other value, I don't know how to vote. I'm not English native speaker, so do you get my idea ? Thanks . – user5746429 Jan 12 '16 at 05:41
  • Considering the standard hough transform your accumulator matrix is only 2D if (and only if) you have a fixed radius (not a range). However, I looked at the OpenCV implementation and they use some tricks to reduce their matrix to 2D in either case. – gfkri Jan 12 '16 at 07:16
  • But I still can't understand. For example, a 100\*100 image (the value of all pixels is 0), and then we draw a circle whose radius is 50 on this image. So **if dp = 2, how to vote and detect it** ? The size of accumulator is 50\*50, I think it's not enough. What do you think ? – user5746429 Jan 12 '16 at 10:56
  • Sorry, I didn't notice your update. And now I understand it, the pixels which are close will be merged. Thank you ! – user5746429 Jan 12 '16 at 11:16