Loading ...
Sorry, an error occurred while loading the content.

Hough transforms

Expand Messages
  • Gary Livick
    I generally get over my head about once a week. Perhaps someone has some information that will get my project going forward. The basic project: Between Kent
    Message 1 of 12 , Aug 1, 2004
    View Source
    • 0 Attachment
      I generally get over my head about once a week. Perhaps someone has
      some information that will get my project going forward.

      The basic project: Between Kent Farnsworth and myself, we have an
      RF-linked Hero 2000 setup that allows controlling the robot via a remote
      host computer, using the robot itself running in its native BASIC from
      the command line as a slave. We use C as the programming language on
      the host. All the library programs have been written for mechanical
      control of the robot's functions, such as motion, sonar scanning, etc.

      The expanded project, phase 1: We have ported the "Grid Nav 1.0"
      grid-based planner, written by Tucker Balch, in its totality. This
      planner allows the Hero to navigate from point A to point B, self
      planning its route around obstacles. We utilize the robot's own PID
      system and odometry capabilities. It operates very effectively.

      The expanded project, phase 2: Using work by Hans Moravec, as explained
      very effectively by Prof. Crabbe at the US Naval Acadamy
      (http://www.cs.usna.edu/~crabbe/2004-01/SI475/classes/mapping/mapping.pdf),
      we have implemented an certainty grid, utilizing a Baysian conditional
      probablily approach, built up from sonar date. We display the results
      on the host screen, and see that we get an excellent representation of
      the local areas around the robot.

      The expanded project, phase 3: This is the over-the-head part. In order
      to make use of the certainty grid for simultaneous localization and
      mapping, we think it will be most expedient to utilize a Hough transform
      approach to both create the global map of the robot's world, and for use
      in later self-localization of the robot within it. That's where I'm
      stuck.

      What is needed is a Schaum's Outline-like straight explanation of the
      Hough transform for generating straight and simple curved lines from an
      occupancy grid (actually converted to an occupancy grid for this
      purpose, which will then represent a coarse bitmap of the environment),
      along with simple example applications written in C, or at least pseudo
      code.

      The work I'm seeing which uses the above approach tends to use MAT-LAB.
      We want to do it all self-contained in our own code.

      Anyone have any pointers to something like this. Anyone doing similar work?

      Thanks,

      Gary Livick




      [Non-text portions of this message have been removed]
    • toddpierce1968
      Gary, You reminded me of graphics programs and why I buy them... so I don t have to do the math myself. And of course, looking at this site reminded me again
      Message 2 of 12 , Aug 1, 2004
      View Source
      • 0 Attachment
        Gary,

        You reminded me of graphics programs and why I buy them... so I don't
        have to do the math myself.

        And of course, looking at this site reminded me again why I don't do
        the math... but gee whiz, ya gotta like the little Java applet they
        put together to illustrate their point (or curve, as it were).

        http://www.cs.nps.navy.mil/people/faculty/capps/iap/class2/splines/

        -Todd

        --- In SeattleRobotics@yahoogroups.com, Gary Livick <glivick@s...> wrote:
        >
        >
        > I generally get over my head about once a week. Perhaps someone has
        > some information that will get my project going forward.
        >
        > The basic project: Between Kent Farnsworth and myself, we have an
        > RF-linked Hero 2000 setup that allows controlling the robot via a
        remote
        > host computer, using the robot itself running in its native BASIC from
        > the command line as a slave. We use C as the programming language on
        > the host. All the library programs have been written for mechanical
        > control of the robot's functions, such as motion, sonar scanning, etc.
        >
        > The expanded project, phase 1: We have ported the "Grid Nav 1.0"
        > grid-based planner, written by Tucker Balch, in its totality. This
        > planner allows the Hero to navigate from point A to point B, self
        > planning its route around obstacles. We utilize the robot's own PID
        > system and odometry capabilities. It operates very effectively.
        >
        > The expanded project, phase 2: Using work by Hans Moravec, as explained
        > very effectively by Prof. Crabbe at the US Naval Acadamy
        >
        (http://www.cs.usna.edu/~crabbe/2004-01/SI475/classes/mapping/mapping.pdf),

        > we have implemented an certainty grid, utilizing a Baysian conditional
        > probablily approach, built up from sonar date. We display the results
        > on the host screen, and see that we get an excellent representation of
        > the local areas around the robot.
        >
        > The expanded project, phase 3: This is the over-the-head part. In
        order
        > to make use of the certainty grid for simultaneous localization and
        > mapping, we think it will be most expedient to utilize a Hough
        transform
        > approach to both create the global map of the robot's world, and for
        use
        > in later self-localization of the robot within it. That's where I'm
        > stuck.
        >
        > What is needed is a Schaum's Outline-like straight explanation of the
        > Hough transform for generating straight and simple curved lines from an
        > occupancy grid (actually converted to an occupancy grid for this
        > purpose, which will then represent a coarse bitmap of the environment),
        > along with simple example applications written in C, or at least pseudo
        > code.
        >
        > The work I'm seeing which uses the above approach tends to use
        MAT-LAB.
        > We want to do it all self-contained in our own code.
        >
        > Anyone have any pointers to something like this. Anyone doing
        similar work?
        >
        > Thanks,
        >
        > Gary Livick
        >
        >
        >
        >
        > [Non-text portions of this message have been removed]
      • raymond melton
        ... Okay, suppose that I am undaunted by mathematics. What is a Hough transform? Regards. __________________________________ Do you Yahoo!? New and Improved
        Message 3 of 12 , Aug 1, 2004
        View Source
        • 0 Attachment
          --- toddpierce1968 <todd_pierce@...> wrote:

          Okay, suppose that I am undaunted by mathematics.
          What is a Hough transform?

          Regards.



          __________________________________
          Do you Yahoo!?
          New and Improved Yahoo! Mail - Send 10MB messages!
          http://promotions.yahoo.com/new_mail
        • Mr S
          Were you looking for information in respect of something specific or just in general? I know its early and the coffee probably hasn t done its job yet, but
          Message 4 of 12 , Aug 2, 2004
          View Source
          • 0 Attachment
            Were you looking for information in respect of
            something specific or just in general?

            I know its early and the coffee probably hasn't done
            its job yet, but google shows 21000 pages that talk
            about the hough transform. My first three choices had
            examples and tutorials.

            --- raymond melton <rtmelton@...> wrote:

            > --- toddpierce1968 <todd_pierce@...> wrote:
            >
            > Okay, suppose that I am undaunted by mathematics.
            > What is a Hough transform?
            >
            > Regards.
            >
            >
            >
            > __________________________________
            > Do you Yahoo!?
            > New and Improved Yahoo! Mail - Send 10MB messages!
            > http://promotions.yahoo.com/new_mail
            >
            >
            > Visit the SRS Website at
            > http://www.seattlerobotics.org
            > Yahoo! Groups Links
            >
            >
            > SeattleRobotics-unsubscribe@yahoogroups.com
            >
            >
            >
            >




            __________________________________
            Do you Yahoo!?
            Yahoo! Mail is new and improved - Check it out!
            http://promotions.yahoo.com/new_mail
          • Gary Livick
            The Hough transform is an algorithm that is used to generate lines, curves, etc., from, for example, pixels in a video image. It can be used to detect shapes,
            Message 5 of 12 , Aug 2, 2004
            View Source
            • 0 Attachment
              The Hough transform is an algorithm that is used to generate lines,
              curves, etc., from, for example, pixels in a video image. It can be
              used to detect shapes, edges, that sort of thing. In the case of
              localization using sonar, using the Bayesian approach we are using
              produces a pixelated image of the space around the robot. Converting
              those pixels into lines greatly facilitates matching the sonar map to an
              a priori line map.

              Gary

              raymond melton wrote:

              >--- toddpierce1968 <todd_pierce@...> wrote:
              >
              >Okay, suppose that I am undaunted by mathematics.
              >What is a Hough transform?
              >
              >Regards.
              >
              >
              >
              >__________________________________
              >Do you Yahoo!?
              >New and Improved Yahoo! Mail - Send 10MB messages!
              >http://promotions.yahoo.com/new_mail
              >
              >
              >Visit the SRS Website at http://www.seattlerobotics.org
              >Yahoo! Groups Links
              >
              >
              >
              >
              >
              >
              >
              >
            • Gary Livick
              Yes, there are many links, just need a practical approach to detecting straight lines in a pixel space, not the theory. I ve been looking for awhile, and
              Message 6 of 12 , Aug 2, 2004
              View Source
              • 0 Attachment
                Yes, there are many links, just need a practical approach to detecting
                straight lines in a pixel space, not the theory. I've been looking for
                awhile, and can't locate anything basic. If necessary, we'll need to
                dig into the theory and work out the application, but was hoping someone
                else had done this already.

                Thanks for responding,

                Gary Livick

                Mr S wrote:

                >Were you looking for information in respect of
                >something specific or just in general?
                >
                >I know its early and the coffee probably hasn't done
                >its job yet, but google shows 21000 pages that talk
                >about the hough transform. My first three choices had
                >examples and tutorials.
                >
                >--- raymond melton <rtmelton@...> wrote:
                >
                >
                >
                >>--- toddpierce1968 <todd_pierce@...> wrote:
                >>
                >>Okay, suppose that I am undaunted by mathematics.
                >>What is a Hough transform?
                >>
                >>Regards.
                >>
                >>
                >>
                >>__________________________________
                >>Do you Yahoo!?
                >>New and Improved Yahoo! Mail - Send 10MB messages!
                >>http://promotions.yahoo.com/new_mail
                >>
                >>
                >>Visit the SRS Website at
                >>http://www.seattlerobotics.org
                >>Yahoo! Groups Links
                >>
                >>
                >> SeattleRobotics-unsubscribe@yahoogroups.com
                >>
                >>
                >>
                >>
                >>
                >>
                >
                >
                >
                >
                >__________________________________
                >Do you Yahoo!?
                >Yahoo! Mail is new and improved - Check it out!
                >http://promotions.yahoo.com/new_mail
                >
                >
                >Visit the SRS Website at http://www.seattlerobotics.org
                >Yahoo! Groups Links
                >
                >
                >
                >
                >
                >
                >
                >


                [Non-text portions of this message have been removed]
              • raymond melton
                ... I m curious about your Bayesian approach. Would you be willing to elaborate a bit on that? Regards, Ray. P.S. Google on Hough transform brings up all
                Message 7 of 12 , Aug 2, 2004
                View Source
                • 0 Attachment
                  --- Gary Livick <glivick@...> wrote:
                  > In the case of
                  > localization using sonar, using the Bayesian
                  > approach we are using

                  I'm curious about your Bayesian approach. Would you
                  be willing to elaborate a bit on that?

                  Regards, Ray.

                  P.S. Google on Hough transform brings up all kinds of
                  bizarre blurbs.



                  __________________________________
                  Do you Yahoo!?
                  Read only the mail you want - Yahoo! Mail SpamGuard.
                  http://promotions.yahoo.com/new_mail
                • Giuseppe Marullo
                  Anybody willing to use Skype to join a multiperson audio chat? It works really well and it is claims to be free. I will do my best to answer if you call me in
                  Message 8 of 12 , Aug 2, 2004
                  View Source
                  • 0 Attachment
                    Anybody willing to use Skype to join a multiperson audio chat? It works
                    really well and it is claims to be free.
                    I will do my best to answer if you call me in the next 4 hours, it can do up
                    to 5 persons at once.

                    Giuseppe Marullo

                    P.S: my username is name dot surname
                  • Gary Livick
                    Bayes Rule has been in use in robotics for building sonar maps since the mid-1980 s or so. A link explaining the mathematics of the rule can be found at
                    Message 9 of 12 , Aug 2, 2004
                    View Source
                    • 0 Attachment
                      Bayes Rule has been in use in robotics for building sonar maps since the
                      mid-1980's or so. A link explaining the mathematics of the rule can be
                      found at http://www.ai.mit.edu/~murphyk/Bayes/bayesrule.html.

                      In essence, the use of Bayes Rule allows one to build up a high
                      resolution rasterized picture of the area around a robot within the
                      range of the sonar. Imagine a room with square tiles on the floor, with
                      a picture of a happy face made with black tiles surrounded by white
                      tiles -- that's a rasterized happy face. But we couldn't see that face
                      directly with sonar (assuming the black tiles are tall), due to the
                      width of the sonar beam. A sonar beam (on the typical Polaroid sonar)
                      is 22 or more degrees wide. Out at a distance of several feet, the
                      sonar might not be able to tell one black monolithic tile from another
                      if they were too close together. If one tile was widely separated from
                      the rest, and we detected it in a sonar beam, we would know there was
                      one there, and how far away it was, but we wouldn't know it's azimuth
                      other than it was within the beam arc at that distance.

                      Sonar strength and reliability varies with distance, and also within the
                      width of the beam at a give distance. The probability that something
                      will or will not be detected at various distances from the sonar
                      emitter, and azimuths from the beam centerline, given the variation in
                      reliability around those factors, is called the sonar model.

                      Bayes rule is a probabilistic framework that allows us to update our
                      knowledge of previous events, given a new event. The updating is based
                      on probability, and the value of the new event is probabilistic (the
                      sonar model in this case).

                      As a simple sonar example, lets say you have a sonar with a range of
                      (barely) 16 feet. The odds that you can detect a narrow object on the
                      beam centerline at 16 feet are not good, certainly not 100%. The
                      probability that you can detect an object at 16 feet that is at one
                      extreme of the beam width is practically zero. So if you got 3 hits
                      out of 18 indicating that there was an object at 16 feet, you would not
                      be too confident that there really was something there. However, if it
                      turns out that your poor probability was due to the object being at one
                      edge of the sonar beam at that distance, as you swung the sonar scan a
                      few degrees at a time into the direction of the object within the beam,
                      your odds of getting a return would improve, and your confidence would
                      also improve that there was something actually there. Using the
                      Bayesian approach is how we develop that probability over a grid space
                      (your tile floor), and it comes out in the form of what is called a
                      confidence grid. Using this method, we can see the happy face with sonar.

                      Extending this, if we can connect the dots in the evidence grid when
                      they represent straight lines, we can identify walls and other objects
                      that we can then compare to known features in a pre-existing map.
                      That's what I want the Hough transform information for. The robot
                      should think it knows where it is at all times using odometry. But
                      errors in odometry build up over time, and need to be corrected before
                      the robot gets hopelessly lost. There are various ways to do this,
                      like, perhaps, using bump sensors and deliberately running into known
                      objects so as to zero out errors in specific axes. Other ways include
                      using sonar, laser range finding, GPS (outdoors with room for position
                      error) and beacons.

                      Hope this helps. I have pointers to research papers on the subject, and
                      C code segments that do the actual work.

                      Best regards,

                      Gary Livick



                      raymond melton wrote:

                      >--- Gary Livick <glivick@...> wrote:
                      >
                      >
                      >>In the case of
                      >>localization using sonar, using the Bayesian
                      >>approach we are using
                      >>
                      >>
                      >
                      >I'm curious about your Bayesian approach. Would you
                      >be willing to elaborate a bit on that?
                      >
                      >Regards, Ray.
                      >
                      >P.S. Google on Hough transform brings up all kinds of
                      >bizarre blurbs.
                      >
                      >
                      >
                      >__________________________________
                      >Do you Yahoo!?
                      >Read only the mail you want - Yahoo! Mail SpamGuard.
                      >http://promotions.yahoo.com/new_mail
                      >
                      >
                      >Visit the SRS Website at http://www.seattlerobotics.org
                      >Yahoo! Groups Links
                      >
                      >
                      >
                      >
                      >
                      >
                      >
                      >


                      [Non-text portions of this message have been removed]
                    • Martin R. Calsyn
                      ... Tantalizing... I (and I suspect others) would be very interested in both the references and the source if you re willing to share it. Very informative -
                      Message 10 of 12 , Aug 2, 2004
                      View Source
                      • 0 Attachment
                        > Hope this helps. I have pointers to research papers on the
                        > subject, and C code segments that do the actual work.

                        Tantalizing... I (and I suspect others) would be very interested in
                        both the references and the source if you're willing to share it.

                        Very informative - Thanks
                        --Martin

                        -----Original Message-----
                        From: Gary Livick [mailto:glivick@...]
                        Sent: Monday, August 02, 2004 6:37 PM
                        To: SeattleRobotics@yahoogroups.com
                        Subject: [SeattleRobotics] Bayesian conditional probability in sonar
                        mapping

                        [...]
                      • Gary Livick
                        Martin, This ambitious work has produced some excellent results using many of the same tools I am developing. Unfortunately, his source, which is free for the
                        Message 11 of 12 , Aug 2, 2004
                        View Source
                        • 0 Attachment
                          Martin,

                          This ambitious work has produced some excellent results using many of
                          the same tools I am developing. Unfortunately, his source, which is
                          free for the downloading, is written in JAVA. But it gives an excellent
                          idea of what can be done with a single sonar module mounted on a servo.

                          http://rossum.sourceforge.net/papers/Localization/PosPosterv4.pdf

                          I'll post some code of mine that will actually display a certainty grid
                          on a screen, given some assumed sonar data. It's written to run under
                          DOS. Just need to put it together from various routines. I'll post
                          both the source (which compiles and runs under Turbo C++, downloadable
                          for free from Borland) and also the .exe file. With a little fiddling,
                          and a sonar of your own on a servo, you can make it your own.

                          Best regards,

                          Gary

                          Martin R. Calsyn wrote:

                          >>Hope this helps. I have pointers to research papers on the
                          >>subject, and C code segments that do the actual work.
                          >>
                          >>
                          >
                          >Tantalizing... I (and I suspect others) would be very interested in
                          >both the references and the source if you're willing to share it.
                          >
                          >Very informative - Thanks
                          >--Martin
                          >
                          >-----Original Message-----
                          >From: Gary Livick [mailto:glivick@...]
                          >Sent: Monday, August 02, 2004 6:37 PM
                          >To: SeattleRobotics@yahoogroups.com
                          >Subject: [SeattleRobotics] Bayesian conditional probability in sonar
                          >mapping
                          >
                          >[...]
                          >
                          >
                          >
                          >Visit the SRS Website at http://www.seattlerobotics.org
                          >Yahoo! Groups Links
                          >
                          >
                          >
                          >
                          >
                          >
                          >
                          >


                          [Non-text portions of this message have been removed]
                        • Lyle Joseph Chamberlain
                          Hi guys, I ve been converting a 1/6 scale rc car to robotic control, complete with an IMU and GPS. More on that later when I have time to put together a web
                          Message 12 of 12 , Aug 11, 2004
                          View Source
                          • 0 Attachment
                            Hi guys,

                            I've been converting a 1/6 scale rc car to robotic control, complete with
                            an IMU and GPS. More on that later when I have time to put together a web
                            page.

                            Here's my problem: yesterday the steering servo burned out for no
                            apparent reason. I built custom servo-driving electronics (a mux from the
                            rx and the uc). The servos run off of a 5-cell NiMH pack. We have used
                            the current circuitry many times before. So yesterday while the car was
                            sitting on the test bench, the servo started
                            smoking and the motor heat sink got pretty warm before I could turn off
                            the power. No commands were being sent (except perhaps a little radio
                            noise, but the servos weren't twitching). The servo was not jammed (as
                            far as I can tell) and the front wheels were in the center of their
                            motion.

                            I opened up the servo. The metal gears were fine, and it had full range
                            of motion. It looks like som surface mount resistors next to a transistor
                            got really hot and melted the case (smoke).

                            The only think I can find wrong with MY circuitry is a loose power
                            connection. The ground pin from the servo batteries was loose. The
                            driving signal (which was inactive?) comes from another battery. Could
                            spotty power cause a nice digital RC servo to get confused and
                            self-destruct? Oh yeah, the throttle servo, a smaller digital, was
                            connected to the same power, and it's fine. I've got to replace the dang
                            thing, but I'm afraid. Anyone ever see anything like this before?

                            Thanks!

                            -Lyle Chamberlain
                          Your message has been successfully submitted and would be delivered to recipients shortly.