Announcement

Collapse
No announcement yet.

Hough Detection/CS question

Collapse
X
Collapse
 
  • Page of 3
  • Filter
  • Time
  • Show
Clear All
new posts
Previous 1 2 3 template Next
  • #1

    Hough Detection/CS question

    There seem to be a number of smart math/cs people on this board so I thought I'd ask this here.

    Lately, as a side project in my AI class, I've been trying to write a program to detect shapes in an image. I've used Canny edge detection and the Hough transform algorithm and my program identifies circles pretty well now.

    Basically, my Hough algorithm starts on an edge point, finds the slope of the line perpendicular to the tangent, and traces that line across the whole image, dropping "votes" in "bins" which cover a certain number of pixels. So I store a tuple containing the x,y coordinate of the original edge point in each "bin" it crosses, so pseudocode/python:
    Code:
    x, xi = [initial x]; y, yi=[initial y]
theta=[angle of perp. line]
dx=cos(theta); dy=sin(theta)
while (x and y are within bounds):
	x+=dx
	y+=dy
	bins[x/binsize][y/binsize].append((x,y))
    …and again for the other side, e.g. x-=dx and y-=dx.

    So I understand how to detect a circle, and my program is pretty good at that. The center will be in the bin with the most elements, and the radius can just be found with the mean of the hypotenuses. But concentric circles are proving to be a bit problematic. My first thought is to try to sort the list of radii, approximate derivatives and try to find outliers in slope. My reasoning is that the points of discontinuity will identify which "votes" belong to which circle. However, there are three problems here: 1) Background noise will show up as discontinuities, so I need to eliminate huge outliers. 2) There might not be enough data points to approximate a good derivative. However since I'm inherently looking at the bin with the most data points, I think it'll be ok. And 3) I know next to nothing about statistics because at my high school it's either calculus or statistics, and I picked calc (no regrets there). I don't have any idea what the mathematical way to identify an outlier would be.

    So then, I have two questions. Is this the wrong way to do it, if so, what's a better way? And second, if it is the right way, how do I/where can I learn how to find outliers?

    I have some very vague ideas on how to detect other shapes like squares or triangles, but I'm having trouble thinking of a particularly good way. Naturally nothing involving this sort of image processing is going to be 100% accurate, but being able to identify "that bit is squarish" and "that bit is kinda round" seems perfectly plausible to me.

    I apologize if this entire post reeks of ignorance. If it does, please keep in mind that I'm just an ignorant high school student
    Thanks in advance for the help!
    If there is no sound in space, how come you can hear the lasers?
    ){ :|:& };:
    Tags: None
  • #2
    Originally posted by Hauldren Collider View Post
    There seem to be a number of smart math/cs people on this board so I thought I'd ask this here.

    Lately, as a side project in my AI class, I've been trying to write a program to detect shapes in an image. I've used Canny edge detection and the Hough transform algorithm and my program identifies circles pretty well now.

    Basically, my Hough algorithm starts on an edge point, finds the slope of the line perpendicular to the tangent, and traces that line across the whole image, dropping "votes" in "bins" which cover a certain number of pixels. So I store a tuple containing the x,y coordinate of the original edge point in each "bin" it crosses, so pseudocode/python:
    Code:
    x, xi = [initial x]; y, yi=[initial y]
theta=[angle of perp. line]
dx=cos(theta); dy=sin(theta)
while (x and y are within bounds):
	x+=dx
	y+=dy
	bins[x/binsize][y/binsize].append((x,y))
    …and again for the other side, e.g. x-=dx and y-=dx.
    It's been a while, but to be clear, you're just implementing a regular Hough transform here? That's what it looks like.

    The Hough transform fails for concentric circles, it's a known limitation. I don't think this is a necessarily dumb question (I've certainly never thought about it). A quick google shows some recent research papers which have devised an algorithm for detecting concentric circles in images, but you need an ACM or IEEE membership to view them.
    "The issue is there are still many people out there that use religion as a crutch for bigotry and hate. Like Ben."
    Ben Kenobi: "That means I'm doing something right. "

    Comment

    • #3
      Yes, it's a regular Hough transform. I've got that bit working, it's figuring out how to interpret the data (is that the correct way to put it?) that's giving me trouble.
      If there is no sound in space, how come you can hear the lasers?
      ){ :|:& };:

      Comment

      • #4
        Ok, thanks. My teacher seemed to imply that it was possible. He said detecting concentric circles was "tricky". So you're saying it's totally impossible to detect them with Hough? Hm.

        But then, what about squares or triangles? I'm fairly confident it's possible to detect those.
        If there is no sound in space, how come you can hear the lasers?
        ){ :|:& };:

        Comment

        • #5
          Originally posted by Hauldren Collider View Post
          Ok, thanks. My teacher seemed to imply that it was possible. He said detecting concentric circles was "tricky". So you're saying it's totally impossible to detect them with Hough? Hm.
          You can use Hough, you just need some Secret Sauce.

          This paper is exactly what you want, but unfortunately is not free:
          http://www.springerlink.com/content/m5rnfeeb76bywe1m/



          But then, what about squares or triangles? I'm fairly confident it's possible to detect those.
          Yep. Those are fairly easy, especially if you got circles working. There should be a ton of examples online as it's a fairly typical homework problem.
          "The issue is there are still many people out there that use religion as a crutch for bigotry and hate. Like Ben."
          Ben Kenobi: "That means I'm doing something right. "

          Comment

          • #6
            Alright, thank you very much! I will check if any of the databases my school has a subscription to have that article somewhere.
            If there is no sound in space, how come you can hear the lasers?
            ){ :|:& };:

            Comment

            • #7
              Found a limited preview of that article. It's missing some pages, of course:

              Pattern Recognition and Image Analysis
              http://bit.ly/94uHo2
              IbPRIA 2005 (Iberian Conference on Pattern Recognition and Image Analysis) was the second of a series of conferences jointly organized every two years by the Portuguese and Spanish Associations for Pattern Recognition (APRP, AERFAI), with the support of the International Association for Pattern Recognition (IAPR). This year, IbPRIA was hosted by the Institute for Systems and Robotics and the Geo-systems Center of the Instituto Superior Tecn ́ ico and it was held in Estoril, Por- gal. It provided the opportunity to bring together researchers from all over the world to discuss some of the most recent advances in pattern recognition and all areas of video, image and signal processing. There was a very positive response to the Call for Papers for IbPRIA 2005. We - ceived 292 full papers from 38 countries and 170 were accepted for presentation at the conference. The high quality of the scienti?c program of IbPRIA 2005 was due ?rst to the authors who submitted excellent contributions and second to the dedicated colla- ration of the international Program Committee and the other researchers who reviewed the papers. Each paper was reviewed by two reviewers, in a blind process. We would like to thank all the authors for submitting their contributions and for sharing their - search activities. We are particularly indebted to the Program Committee members and to all the reviewers for their precious evaluations, which permitted us to set up this publication.


              Edit: Bingo, here's the full paper: http://www.pdfone.com/download/7_key...ic-circles.pdf
              "The issue is there are still many people out there that use religion as a crutch for bigotry and hate. Like Ben."
              Ben Kenobi: "That means I'm doing something right. "

              Comment

              • #8
                It actually looks pretty simple. Just need to use the Bresenham line algorithm with Cramer's rule in addition to the Hough transform.

                Glad someone else figured it out for us.
                "The issue is there are still many people out there that use religion as a crutch for bigotry and hate. Like Ben."
                Ben Kenobi: "That means I'm doing something right. "

                Comment

                • #9
                  So...basically my idea wasn't even close
                  Darn.

                  Though...Cramer's rule is O(n!), right? That's really slow.
                  If there is no sound in space, how come you can hear the lasers?
                  ){ :|:& };:

                  Comment

                  • #10
                    Originally posted by Hauldren Collider View Post
                    So...basically my idea wasn't even close
                    Darn.

                    Though...Cramer's rule is O(n!), right? That's really slow.
                    Yes, very. Gaussian elimination is far more efficient and might be able to get you the same thing, but I'm far too rusty at this stuff to take a shot at it.
                    "The issue is there are still many people out there that use religion as a crutch for bigotry and hate. Like Ben."
                    Ben Kenobi: "That means I'm doing something right. "

                    Comment

                    • #11
                      Gaussian elimination/row reduction is still something like O(n^3), but that's still much better than O(n!)

                      And everything is faster than being totally unable to solve the problem. Thanks for all the help, I will try this out and see how it goes.
                      If there is no sound in space, how come you can hear the lasers?
                      ){ :|:& };:

                      Comment

                      • #12
                        By the way, what kind of high school do you go to? Jesus.
                        "The issue is there are still many people out there that use religion as a crutch for bigotry and hate. Like Ben."
                        Ben Kenobi: "That means I'm doing something right. "

                        Comment

                        • #13
                          The best! (according to US News and World Reports, anyway)
                          https://www.tjhsst.edu

                          Our website kinda sucks now. I'm one of the students that runs the school's computer system. Believe me, we had another proposal for the design, this one wasn't our choice
                          If there is no sound in space, how come you can hear the lasers?
                          ){ :|:& };:

                          Comment

                          • #14
                            Originally posted by Asher View Post
                            but I'm far too rusty at this stuff to take a shot at it.
                            Tic toc

                            Know the feeling
                            With or without religion, you would have good people doing good things and evil people doing evil things. But for good people to do evil things, that takes religion.

                            Steven Weinberg

                            Comment

                            • #15


                              KH FOR OWNER!
                              ASHER FOR CEO!!
                              GUYNEMER FOR OT MOD!!!

                              Comment

                              Previous 1 2 3 template Next
                              Working...
                              X