tag:blogger.com,1999:blog-81758634596920852024-03-06T01:10:49.368-05:00NinjinuityNinjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.comBlogger56125tag:blogger.com,1999:blog-8175863459692085.post-37476437148665530272014-03-23T20:32:00.000-04:002014-03-23T20:32:00.176-04:00Extending SRP's guarantees to validated registration<br />
<i>This post is about work done jointly with Michael Sanders and Jacob Hurwitz for 6.858 (One of MIT's Computer System's Security courses).</i><br />
<br />
The <a href="http://srp.stanford.edu/">Stanford Remote Password Protocol</a> is a really amazing little piece of cryptography. Like almost every great crypto-system, it provides seemingly impossible guarantees. Namely, it allows a server to recognize a client without having any real usable information about them.<br />
<br />
In most authentication systems, the server is at some point in time privy to sufficient information to impersonate the user: perhaps you send your password to Google, Microsoft, or Facebook, or perhaps you send a hash. Regardless, as some point in the process, the server sees enough information about your password to fake a login later. With SRP, this isn't the case. To quote the <a href="http://srp.stanford.edu/">SRP website</a>:<br />
<blockquote class="tr_bq">
SRP is a secure password-based authentication and key-exchange protocol. It solves the problem of authenticating clients to servers securely, in cases where the user of the client software must memorize a small secret (like a password) and carries no other secret information, and where the server carries a <i>verifier</i> for each user, which allows it to authenticate the client but which, if compromised, would not allow the attacker to impersonate the client. In addition, SRP exchanges a cryptographically-strong secret as a byproduct of successful authentication, which enables the two parties to communicate securely.</blockquote>
Still, there is a slight problem with SRP, if you're willing to crimp down your tinfoil hat a little.<br />
<a name='more'></a><br />
<a href="https://www.blogger.com/null" name="more"></a>As specified, SRP does not allow the server to check that a password is strong without violating it's own security principals. Sure, the server can push some javascript out to users to do the checking for them, but that has problems of its own:<br />
<br />
<ol>
<li>A really malicious user might be able to bypass the checks by modifying the javascript.</li>
<li>A really paranoid / low-level user might disable javascript or insist on running their own code.</li>
<li>A really malicious / stupid server or other entity might take the opportunity to sneak some code into the password checking code that ruins guarantees by shipping code back serverside for checking.</li>
</ol>
It's also ambiguous what a "strong password" really is. In fact, many strong password requirements actually weaken the space of passwords users chose from, or at least doesn't really improve the situation. One way to specify the strength of a password by the <a href="http://en.wikipedia.org/wiki/Entropy_(information_theory)">Information-Theoretic Entropy</a> of the process used to create it. This definition is nice in theory, and a good model of truly secure passwords: the best passwords are generated completely at random.<br />
<br />
It's also super inconvenient to remember totally random passwords. I've actually got another post on exactly that coming up, so hang tight there and pretend that we actually do want totally random passwords.<br />
<div>
<br /></div>
<div>
The work myself and my group members did augmented SRP to handle ensuring that users pick totally random passwords without revealing those passwords in the process. The basic idea (exchanging DL commitments then revealing them to the user), is pretty simple, but it took us a little while to come up with and we couldn't find another instance of someone else doing the same thing in a practical manner. I'm perhaps unjustifiably proud of our work.</div>
<div>
<br /></div>
<div>
<a href="http://css.csail.mit.edu/6.858/2013/projects/woursler-jhurwitz-mssand.pdf">Our paper is hosted on the 6.858 website.</a> It is also <a href="https://github.com/Zomega/lab6858/raw/commitments/documentation/paper.pdf">mirrored on github</a>, <a href="https://github.com/Zomega/lab6858/tree/commitments">where we keep our example code</a> (full credit and awe to Jacob Hurwitz for putting together an excellent demo on a tight timetable).</div>
<div>
<br /></div>
<div>
That said, what we have done has its flaws. For one we introduce a partition attack into SRP, which we suggest resolving by rate limiting login attempts and increasing SRP's security parameter. We also require more client side computation than standard SRP, and that's computationally taxing enough that logins can take upwards of a second even largely ignoring network delays. Finally we have to introduce a few changes to SRP that make it harder to optimize on the server.</div>
<div>
<br /></div>
<div>
Without more auditing and investigation, I can't recommend our protocol for practical use, but I'd love to see it get some further analysis, because I think it presents a practical candidate solution to an interesting problem.</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-21002968824394912542014-03-21T12:58:00.000-04:002014-03-21T12:58:07.606-04:00It's been a while!I haven't forgotten about this blog! I've just been a tad busy recently.<br />
<br />
I've got a bunch of projects (mostly classwork, I confess) I plan to post soon, so check back in a week or so!<br />
<br />
~NinjinuityNinjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-47357601562038004792013-03-04T23:29:00.001-05:002013-03-04T23:29:59.685-05:00Voice Controlling Hexy(This post is a bit rough, but I figured I should get it out there, since I won't be working on Hexy for a little while.)<br />
Before we get started:<br />
<ol>
<li>The code used to make this all work is on Github. I'm new to ROS, so I don't claim that it's set up correctly.</li>
<li>To get things to ROSLaunch nicely, I had to make some pretty hacky changes to how PoMoCo deals with directories. Basically, it now has to use full paths to every directory ( these paths are created at runtime using __file__ ). I haven't seen it fail yet, and I can't think of a specific failure mode, but it makes me very uncomfortable, and I'm looking for a way to change it.</li>
<li>ROSPoMoCo isn't a full substitute for PoMoCo yet. Offsets, for instance, can't be set in ROS, though they are loaded from the .cfg file.</li>
</ol>
<br />
After a bit of hacking, I've ported most of PoMoCo over to run as a ROS Node. This node listens for new moves on the /moves topic and runs them if it is able to (If it can't find the move, it issues a Warning and ignores it).<br />
<br />
At this point, it's time to take advantage of ROS to do neat stuff with Hexy. At first, I wasn't sure what exactly I wanted to do, but some Googling brought up this blog post, <a href="http://www.pirobot.org/blog/0022/">in which an iRobot create is controlled by voice</a>. The package used to do this is perfect for controlling something like Hexy -- <a href="http://ros.org/wiki/pocketsphinx#">pocketsphinx</a> will broadcast any recognized phrase on the \output topic, and the set of recognized phrases can be set with a text file.<br />
<br />
<a name='more'></a><br />
<br />
Sadly, that tutorial is for ROS electric. I'm running ROS groovy on a much newer version of Ubuntu, so some of the instructions need tweaking. In the interest of passing on inspiration and aid, I've include the rough equivalent of the Pi Robot instructions below. Pi Robot deserves credit for these. I mean this section only as a tutorial, an I'm not claiming it's my original work.<br />
<br />
First, grab the pocketsphinx gstreamer plugin.<br />
<br />
<pre style="background-color: #f3f5f7; border: 1pt solid rgb(174, 189, 204); font-family: courier, monospace; font-size: 15px; padding: 5pt; white-space: pre-wrap; word-wrap: break-word;">$ sudo apt-get install gstreamer0.10-pocketsphinx</pre>
Next, grab the ROS wrapper for pocketsphinx. The ROS Wiki says this is located in an SVN repo at <br />
http://albany-ros-pkg.googlecode.com/ but this repo says it is no longer maintained and recommends using https://github.com/mikeferguson/pocketsphinx.git instead. Since this repo is, as of the time of writing, actively maintained, I will use it.<br />
<div>
cd into the appropriate ROS workspace ( it should be in your ROS_PACKAGE_PATH ) and run the following:</div>
<div>
<br />
<pre style="background-color: #f3f5f7; border: 1pt solid rgb(174, 189, 204); font-family: courier, monospace; font-size: 15px; padding: 5pt; white-space: pre-wrap; word-wrap: break-word;">$ git clone https://github.com/mikeferguson/pocketsphinx.git</pre>
<pre style="background-color: #f3f5f7; border: 1pt solid rgb(174, 189, 204); font-family: courier, monospace; font-size: 15px; padding: 5pt; white-space: pre-wrap; word-wrap: break-word;">$ rospack profile</pre>
Everything should be set up now. To check, type the following:<br />
<div>
<pre style="background-color: #f3f5f7; border: 1pt solid rgb(174, 189, 204); font-family: courier, monospace; font-size: 15px; padding: 5pt; white-space: pre-wrap; word-wrap: break-word;">roscd pocketsphinx</pre>
You should cd into the appropriate directory. If you get an error, check your ROS_PACKAGE_PATH.</div>
<div>
At this point, you should be able to demo pocketsphinx.</div>
<div>
<div>
<pre style="background-color: #f3f5f7; border: 1pt solid rgb(174, 189, 204); font-family: courier, monospace; font-size: 15px; padding: 5pt; white-space: pre-wrap; word-wrap: break-word;">roslaunch pockersphinx voice_cmd.launch</pre>
</div>
<br />
Once it starts, try saying things like "forward", "backward", "move right", etc. You should see these phrases printed on the terminal shortly after you say them. (Note that pocketsphinx is quite sensitive to noise) These are being broadcast on recognizer/output.</div>
<div>
<br /></div>
<div>
Congrats! The setup work is done, and there's very little coding left to hook everything up. In fact, hacky translator I wrote takes only 51 lines of python, most being a dictionary to match phrases to the moves hexy knows how to do.<br />
<br />
I've written a .launch file for all of the above, so assuming you've got <a href="https://github.com/Zomega/ROSPoMoCo">my (pre-alpha) ROSPoMoCo package </a>profiled, you should be able to plug in hexy and a mic, and type<br />
<br />
<pre style="background-color: #f3f5f7; border: 1pt solid rgb(174, 189, 204); font-family: courier, monospace; font-size: 15px; padding: 5pt; white-space: pre-wrap; word-wrap: break-word;">$ roslaunch ROSPoMoCo voice-control.launch</pre>
<br />
After a few seconds to allow for the rosnodes to start, say "get up" or similar. Be warned that as of the time of writing, there is not a voice command / ROS service to disengage the servos. You'll need to pull the plug manually.</div>
<div>
<br /></div>
</div>
Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-76157846801041267242013-03-02T16:31:00.001-05:002013-03-02T16:31:37.769-05:00Starting out with ROSThis is going to be a pretty short post with the purpose of motivating future posts on related subjects.<br />
<br />
I've got a lot of really cool robotics equipment now; <a href="http://arcbotics.com/products/hexy/">a stock Hexy</a>, <a href="http://aeroquad.com/content.php">a Cyclone Quadrotor</a>, <a href="http://www.amazon.com/Kinect-Sensor-Adventures-Xbox-360/dp/B002BSA298">a Kinect</a>, and a MakerBot Thing-O-Matic top the list, at the moment.<br />
<br />
Unfortunately, a lot of these pieces of Hardware come with relatively little software behind them. Hexy, for instance, has the short-but-sweet <a href="https://github.com/ArcBotics/PoMoCo">PoMoCo software</a> to start. PoMoCo is great, but it's not very functional; by default, it allows only for interpolation between pre-programmed sequences of joint angles. It's very easy to pick the wrong combination of moves and get Hexy stuck in some contorted pose ( and you can forget about variable speed gaits ).<br />
<br />
This isn't really PoMoCo's fault. Like Hexy, PoMoCo is designed to be a lightweight tool for beginners who can go on to use the platform for other things.<br />
<br />
So, what's next for me on the Software side of Hexy? First off, I want to integrate Hexy with ROS (more on ROS in a later post). At first, I'm just going to hook PoMoCo into ROS and control it from the command line, but I plan on splitting PoMoCo into three ROS nodes, with the eventual goal of augmenting one of them with good gait generation and motor planning, and replacing the other with a series of ROS services to utilize Hexy from any ROS interfaced program.<br />
<br />
In any case, I'll be working on Hexy when I don't have to tool, and tooling when I can to get as much work in on Hexy. I'll keep you posted.Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-84005310456995044702012-06-17T18:34:00.000-04:002012-06-17T18:34:07.586-04:00Voroni Diagrams and Graphs IV: Efficient Computation of the Graph and it's simplexes.Before we jump into algorithms, a few things. The algorithm I'm about to lay out is a version of the Bowyer-Watson algorithm I've referenced in a previous post. It's been pretty heavily modified since, and it was not my initial intent for it to be thins similar. Nonetheless, I think that my implementation has better asymptotic time than any implementation of the original I've yet seen, since (as we'll see) the most intensive parts of the algorithm (most of which were related to searches over the point set) have been offloaded to a simple graph search. We'll also be looking at things through the lens of the Voroni Graph, rather than the Delaunay Triangulation.<br />
<br />
<a name='more'></a><br />
<br />
This brings us to a second key difference between what I'm about to propose and Bowyer-Watson, and it's not as nice as an improved asymptotic time. While Bowyer-Watson returns exactly the set of simplexes which are the Delaunay triangulation, what I'm about to lay out will find all simplexes in the Voroni Graph. These simplexes include the entire Delaunay triangulation, but it may also contain a few extras. While in large real world data sets, I suspect that the occurrence of these extra triangles will be fairly rare, it is pretty easy to cook up examples which will produce arbitrarily many extra triangles. The simplest ones we covered in the last post in this series.<br />
<div>
<br /></div>
<br />
I've looked for a way to naturally check for these triangles during the course of the algorithm, and I've found a few, but I haven't really explored what they do to average run time (I'm not optimistic, since I think the required circumsphere checks are fairly expensive.), so I'll hold off explaining them until a later post when I've implemented enough of this to actually do some testing. In the mean time, I think the simplest thing to do is just to check each simplex we get afterwards, since, again, I think that for a realistic data sets, the incidence of these false positives will be very low.<br />
<br />
On to the actual algorithm. In the first post of this series, we laid out a fairly inefficient method for creating the Voroni graph. In essence, for each point, we thought about combining every possible Voroni graph the point could be in, then we eliminated connections that we found were redundant. If you tried to implement this algorithm naively, you probably noticed that it didn't scale very well. The reason for this is pretty simple. For each of n points, we found (n-1) simple graphs. For each of these new graphs, we compared it to (on average) a less than (n-1)/2 other graphs to decide if it was indeed part of the cell of our point. Therefore, we'd expect our runtime to be O(n<sup>3</sup>). There's a lot of checking going on under the hood there, and while this isn't a horrible asymptotic time, it's not a terribly practical one either. Using the properties of the Voroni graph itself, we can do much better.<br />
<br />
There's also an even bigger problem with the naive approach. It doesn't help us find the Delaunay Triangulation of the set at all. Even once we have the Voroni Graph, we will still need to search it for triangles. With a naive approach, this operation is O(n<sup>3</sup>). While there are obviously improvements we can make to a naive guess and check approach, I claim this is also unnecessary.<br />
<br />
I propose the following approach: the addition of a single point to set of points will only change that set's Voroni graph near the new point, and it will only change the graph in very specific ways. For instance, the addition of a new point will never cause the formation of an edge between two other points that previously did not have an edge. Since we can check to see if there will be an edge between any point in the graph and any new point ( We laid out the groundwork in part I of these posts. ), we can easily create both the Voroni Graph and the exhaustive list of (candidate) Delaunay triangles in this graph as follows:<br />
<br />
<ol>
<li>Initialize an empty list of triangles (or similar) T, and an empty Graph V.</li>
<li>For each point p in our list of points to add to the graph...</li>
<ol>
<li>Use a greedy search to find a vertex in V ( call it q ) which will have an edge with p. If there is no such q ( A.K.A. V is empty ) continue to the next point .</li>
<li>(Recursive) Add the edge between p and q. Check the neighbors of q to see if they have edges with p and or no longer form edges with q.</li>
<ol>
<li>For each neighbor q' that no longer forms an edge with q</li>
<ol>
<li>remove any triangles involving the edge qq'.</li>
</ol>
<li>For each q' that does form an edge</li>
<ol>
<li>check the neighbors of q' for all of the above, and so on.</li>
</ol>
</ol>
<li>Look for new triangles involving p.</li>
</ol>
</ol>
<div>
That's it! If you've ever seen the Bowyer-Watson algorithm, you'll probably recognize what I've done above. I'd go so far as to say that what I've written down above IS Bowyer-Watson, just mathematically rephrased to take advantage of an associated graph.<br />
<br />
It's worth noting that step 2, while, as we'll see, constant time, it's not as trivial as I've made it out to be, especially if we are trying to optimize our implementation. We'll devote the next post more or less exclusively to this topic.</div>
<div>
<br />
Back on topic: What kind of runtimes do we get out of this scheme? Let's review what we know figured out in the second post of this series:<br />
<ul>
<li>Each node of a sufficiently large graph has on average 6 neighbors. ( AKA The number of edges is O(1) ).</li>
<li>(Conjectured) Given a 2D point (and no other information), it takes <span style="text-align: left;">O( n</span><sup style="text-align: left;">1/2</sup><span style="text-align: left;"> )</span> time to find a node that will have an edge with that point.</li>
</ul>
</div>
<div>
Suppose we have a list of n points for which we wish to find T and V.<br />
<div style="text-align: left;">
Clearly, step 1 is O( 1 ). The asymptotic runtime of step 2, can be found as follows: suppose we are adding a point when V has m elements (m is still large enough we can neglect special cases). We'll take <span style="text-align: left;">O( m </span><sup style="text-align: left;">1/2</sup><span style="text-align: left;"> ) steps to find the first point with an edge, but because the number of neighbors of each node is constant, the rest should be O( 1 ) (assuming, of course, that are triangles are stored in an appropriately fast data structure for this sort of. If they are not, we may not be O( 1 )).</span></div>
<div style="text-align: left;">
<span style="text-align: left;"><br /></span></div>
<div style="text-align: left;">
<span style="text-align: left;">To approximate the total runtime of step two, let's use our definition for big-O notation to say that each run will take less than a *</span> m<sup>1/2 </sup>for some constant a. Summing this from m = 0 up until m = n,</div>
<div style="text-align: left;">
we will get an expression for how long step two will complete. Clearly, we've got at worst O( n<sup>3/2 </sup>) time, since we can use that m<sup>1/2</sup> <= n<sup>1/2 </sup>to get a total time less than a * n<sup>3/2</sup>. This may seem like a big, rather unfavorable approximation, but I think it's just about the best we can do without mucking things up. I'll put a link to the Wolfram Alpha Query you can use to gain some insight <a href="http://www.wolframalpha.com/input/?i=series+expanson+sum+sqrt%28m%29+for+m+from+0+to+n">here</a>. Look at the expansion for infinite n in particular. Notice that the highest power is n<sup>3/2</sup>. It's those negative terms that are problematic, but likely not significant.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
<span style="text-align: -webkit-auto;">Also, if we need to check each triangle in T to make sure it is Delaunay, however, we'll get an additional step that is</span><span style="text-align: -webkit-auto;"> O(</span>n<sup>2</sup><span style="text-align: -webkit-auto;">), since there are O(n) triangles at the end of the day, and without additional cleverness, each circumcircle check is itself O(n). Honestly, this is probably the limiting step for this algorithm, and it's something that, as previously mentioned, needs a lot of work.</span></div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Regardless, even though O( n<sup>3/2 </sup>) to find the Voroni Graph is a <u>lot</u> better than O( n<sup>3 </sup>), I claim that we can probably pare it down even further to O( n * log( n ) ) with some work. If all goes as planned, we'll talk about my reasons for that claim (and potentially an implementation) in the next post.</div>
<div style="text-align: left;">
<br /></div>
Also in the next post(s):<br />
<br />
<ul>
<li>I'll (hopefully) have some C++ code on github to demonstrate all this.</li>
<li>I'll post some test data which I've collected from several sources, including the original scans from the Stanford Bunny, all in a common format we'll be using from here on out.</li>
<li>We'll talk about extending the algorithm presented here to allow us to merge two (or more) preexisting Voroni Graphs together.</li>
<li>We'll also start to talk about practical applications for the Delaunay triangulation and closely related ideas.</li>
</ul>
</div>Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-41096978200557192902012-06-15T20:00:00.000-04:002012-06-22T12:49:52.896-04:00A Simple 2D Graphics Engine Powered by OpenGL/GLUT.In the course of coding up my ideas on the Voroni Graph, it became apparent that a CLI wasn't going to cut it. I needed some sort of graphical library, both for the final visualization, and for debugging. For this, I've chosen to use OpenGL with my own wrappers on top. This is a log of what I've been working on for the past few evenings.<br />
<br />
This is, without the slightest doubt, overkill for what I'm doing right now (2D, very few colors, order of 100 different positions.). Screw that, I'm using OpenGL anyways. Why? I want the experience, and I want to write my own graphics engines that won't be limited by the underlying platform.<br />
<br />
In any case, the process of getting to where I am now has been fairly frustrating. The documentation for all sorts of things involving OpenGL on the web is scant and often contradictory. Some things didn't work, other important aspects of a simple program had been depreciated. Getting even a blank screen to compile was a significant achievement.<br />
<br />
In any case, this was all difficult enough to warrant a post and some preliminary code. Below is a sort of black box on the whole process, written as I worked through everything. For this reason, please excuse the weird tenses.<br />
<a name='more'></a><br />
<h2>
Setup</h2>
<h3>
The install</h3>
I'm running Ubuntu 11.10 Oneiric Ocelot. If you're running anything else, you're pretty much on your own. Sorry, but like I said, this seems to be complicated.<br />
<br />
You'll need build-essentials / g++ or a substitute.<br />
<br />
sudo apt-get install build-essentials<br />
<br />
You'll need glut and gl dev versions.<br />
<br />
sudo apt-get install freeglut3 freeglut3-dev<br />
<br />
If you're running a new version of Ubuntu ( >= 11.10 apparently, when the linking problem this fixes went into effect ) you'll also need to get the package below.<br />
<br />
sudo apt-get install binutils-gold<br />
<br />
After all this, I had no further problems. If you run into errors further down the road, Google is your friend (or, in the case of OpenGL, your somewhat grudging acquaintance).<br />
<br />
<h3>
Testing</h3>
<div>
[[[LINK TO INITIAL TESTING CODE ON GITHUB]]]</div>
<h2>
Design</h2>
<div>
At this point, I sat down and started to write out a list of things I'd want out of my Engine, in an ideal world.</div>
<div>
<ul>
<li>I want to use this engine to do visualizations of algorithms, many of which may very well not be real time.</li>
<li>I don't want to have to structure my program around the visualization.</li>
<li>I want to write something that can work equally well in console or GUI.</li>
<li>Ideally, I want the guts of the engine to run in it's own process, and not depend on the rest of the program at all.</li>
<li>I want a high level interface to my Geometry classes, and I don't want to have to modify these classes to use a GUI.</li>
<li>I want to be able to transfer a lot of the framework from this 2D engine to 3D when the time comes.</li>
</ul>
<div>
From these, we get a few hints about our design.</div>
<ul>
<li>The engine should be a module, possibly in it's own namespace, possibly (shudder) a Singleton. This will make porting it over to it's own process later much easier.</li>
<li>The engine will need to keep track of all the objects it's rendering at a given time, so that it can render asynchronously from whatever process is populating it.</li>
<li>The engine needs to rely on the geometry module, possibly pretty heavily. However, beyond high level design, the converse should not be true. The geometry module should NOT in any way require the graphics engine.</li>
</ul>
<div>
With these in mind, it's now possible to start laying out a preliminary structure in code. We'll have a GraphicsEngine class, which to begin with, I'll treat like a Singleton by instantiating a single global instance (which will be a pointer).</div>
</div>
<div>
<br /></div>
<h2>
Code</h2>
<div>
From there, I proceed by my favorite method: namely coding by re-factoring. I start with the 2D example above, and start to move code around, making sure everything still works every couple of minutes. Pretty early on, I imported the Vector class I wrote for making Lines ( Vector represents points in R^2. It is not related to stl::vector, which I also use quite a bit. ), and switch everything over to that. I made a Color class that holds RGB values, and switch color related code over to that. I made naive structs for triangles, line segments, and polygons, and switch over to those. I keep in mind that all these structs will eventually be classes in Geometry, and I should not specialize them for graphics in any way.</div>
<div>
<br /></div>
<div>
Now, everything I've worked on got wrapped into GraphicsEngine as a class, and I put in a quick global GraphicsEngine* refrence for testing. Drawing a cyan triangle looked like this:</div>
<div>
<blockquote class="tr_bq">
GRAPHICS->setColor( CYAN );<br />
[Initiate Triangle* triangle]<br />
GRAPHICS->renderTriangle( triangle );</blockquote>
</div>
<div>
A few things of note. Of course, this code is completely synchronous. The triangle is remade each time the screen refreshes. Also, the color is set independently of the triangle. Most of this code creates the triangle, and that won't stay constant at all, so take it with a grain of salt.</div>
<div>
<br /></div>
<div>
After this, I took a slight break from the graphics engine to flesh out LineSegment into a proper class, and I changed my test scene slightly based on the new LineSegment class and a few other factors not worth mentioning. Mostly my own personal sense of what looked neat. LineSegment also got it's own file (linesegment.h).</div>
<div>
<br /></div>
<div>
Then, I moved tons of code internal to GraphicsEngine, and made everything static. Importantly, the render function is now a private member function of GraphicsEngine. </div>
<div>
<br /></div>
<div>
I think, in an ideal world, I really ought to be using a namespace at this point instead of a giant static class. Nonetheless I like to think of the GraphicsEngine as an object, not just a collection of functions. Also, more practically, I want to have private members of GraphicsEngines, and I don't think that there's a way to do that with namespaces. Correct me if I'm wrong.</div>
<div>
<br /></div>
<div>
Notably, I do not know how to do anything besides refresh forever at this time. I'm going to work on that after implementing a few more basic features.</div>
<div>
<br />
I then proceeded to add a GraphicsObject class private to the Graphics Engine. This class contains a void* to the object data, and an enum (GraphicsType, also internal and private.) which indicates the type. A static private member GraphicsEngine::objects was added to hold various GraphicsObject instances. The render function was also updated to render objects from GraphicsEngine::objects, render functions were changed to private scope, and a number of overloaded (and public) add( Object ) functions were added.<br />
<br />
Next, a camera Transform was added. This transform is applied to every point when it is drawn. As a proof of concept, this transform was set to cause a slow rotation ( 0.001 radians per rendered frame ).<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-lAmuTFZ8-qGQ5cNiVBsaUzkmlcNaBu5-sDglKc3mk1kYlv28Tv6zkelnXBb3AVxG8rmQG5r4_MFswCVf0kPbeBN55J7Fi5dyOCTqWA8XYLoH2cJ2Bmt8rj9gZqlz9DGnHHnaEIG-Tw/s1600/Points+and+Regular.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="211" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-lAmuTFZ8-qGQ5cNiVBsaUzkmlcNaBu5-sDglKc3mk1kYlv28Tv6zkelnXBb3AVxG8rmQG5r4_MFswCVf0kPbeBN55J7Fi5dyOCTqWA8XYLoH2cJ2Bmt8rj9gZqlz9DGnHHnaEIG-Tw/s320/Points+and+Regular.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span style="font-size: small; text-align: -webkit-auto;"> Test scene with regular </span><span style="font-size: small; text-align: -webkit-auto;">polygons</span><span style="font-size: small; text-align: -webkit-auto;"> and points.</span></td></tr>
</tbody></table>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg2JvCq6FoYbKwaYtDhK7mHPKCiV0Iq4LvDVstwvAUbjHoUD1s-aJ2CEubK20cFTeP1WraL8PfTPQVBzp2i3-i8f9-UdBvxA8mbN9h9e85_DbIf1PpnHz0SIuSWYSG6W6xBVlwb2sWMbA/s1600/graph.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="281" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg2JvCq6FoYbKwaYtDhK7mHPKCiV0Iq4LvDVstwvAUbjHoUD1s-aJ2CEubK20cFTeP1WraL8PfTPQVBzp2i3-i8f9-UdBvxA8mbN9h9e85_DbIf1PpnHz0SIuSWYSG6W6xBVlwb2sWMbA/s320/graph.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Random graph with 100 points and 50 edges.</td></tr>
</tbody></table>
<br />
<br />
Right now, I'm working on rescaling the graphics as window sizes change. Also, I'm preparing to push everything to a GitHub project and link that here. In the meantime, if you notice me doing something stupid, let me know!<br />
<br />
~Ninjinuity</div>
<br />
<br />Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-27623856423873078132012-06-08T08:39:00.002-04:002012-06-08T08:40:22.213-04:00Prelude and FugueThere's a long story behind these: Basically, they were written for me in about 10 minutes during orientation after an off comment that I played the cello. Yes this is in pen (though I did enhance the contrast). Hit the break to see scans...<br />
<a name='more'></a><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRF_b_8jKnOmdkmc1xsVnYhdJBXY_LY9nW62lqpKRuq2h4-dH0Kq50-H4K8rJK_0TrvrLoKsmQ3ts_IlwzPbVhN1eL-AbJXp171fqhm0RXs4WtqEVN3faKrxv3clvU7wm_TdWxJdeXbQ/s1600/PF1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRF_b_8jKnOmdkmc1xsVnYhdJBXY_LY9nW62lqpKRuq2h4-dH0Kq50-H4K8rJK_0TrvrLoKsmQ3ts_IlwzPbVhN1eL-AbJXp171fqhm0RXs4WtqEVN3faKrxv3clvU7wm_TdWxJdeXbQ/s400/PF1.png" width="320" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhobXCTbwhPdEjtMJe0CNg4ptkFY0CsOdKVQbyMZBqxWLqc0zAICk7ldyLsr9dFyYW8Rdg98ELZD4s5_BVcL11kELMDSpv4UOZ5V6AgqLEMhiZXluJbaQjjvBJCbHc9kCsciNewVtNhzQ/s1600/PF2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhobXCTbwhPdEjtMJe0CNg4ptkFY0CsOdKVQbyMZBqxWLqc0zAICk7ldyLsr9dFyYW8Rdg98ELZD4s5_BVcL11kELMDSpv4UOZ5V6AgqLEMhiZXluJbaQjjvBJCbHc9kCsciNewVtNhzQ/s400/PF2.png" width="318" /></a></div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi3_zX-HmPsTZuTR3SfAajsK6FAaMGZzQsOn6OmhbXBaJzm6X2xoSsbrcRRgUZ4sGSg9iw2yrog35PefJKPhWiLMyctRd0aYvSG7CGgBw63dgL7CRcOCx2MQsOs4HmoYlNaueOlEtVbzw/s1600/PF3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi3_zX-HmPsTZuTR3SfAajsK6FAaMGZzQsOn6OmhbXBaJzm6X2xoSsbrcRRgUZ4sGSg9iw2yrog35PefJKPhWiLMyctRd0aYvSG7CGgBw63dgL7CRcOCx2MQsOs4HmoYlNaueOlEtVbzw/s400/PF3.png" width="320" /></a></div>
<br />Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-88137952705105097242012-06-07T23:01:00.000-04:002012-06-08T09:20:09.816-04:00Voroni Diagrams and Graphs III: The Dual.<span style="text-align: left;">In this post, I'll write about the geometric significance of the dual of the Voroni graph and try to convince you that we can extend our discussion, which has so far focused on two dimensions, up to three-dimensions with only some minor changes ( I'll conjecture that the relationships I'm about to lay out extend much beyond that, but I don't have much proof of this ).</span><br />
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">First, though, we need to discuss what a dual is.</span><br />
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">The dual of a graph is itself another graph. Basically every face in the graph is a node in the dual, and two nodes in the dual have an edge between them if ( and only if ) their two corresponding faces share an edge (corners don't count).</span><br />
<span style="text-align: left;"><br /></span><br />
<div style="text-align: left;">
The dual of a planar graph is itself a planar graph, and I claim that the dual of the dual of a graph is the graph itself (with the caveat that we discuss in the next paragraph). The figure below hints at a proof for this (note the crossing edges), though I'm not going to formalize it.</div>
<div style="text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpVs_YVeZn_4Eqwsg4-YB7s28Xt60UUQZS_kMwNaRLfJ12RmsMjAFmstHyMrROlgTsTSFZEwpnapBsu5nB6LSC9o7NWPLfm0jZmUE__JMgOQg-Bles4RXYgbDyLp9D716E56hL07R2Ng/s1600/VGIIIfig1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="242" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpVs_YVeZn_4Eqwsg4-YB7s28Xt60UUQZS_kMwNaRLfJ12RmsMjAFmstHyMrROlgTsTSFZEwpnapBsu5nB6LSC9o7NWPLfm0jZmUE__JMgOQg-Bles4RXYgbDyLp9D716E56hL07R2Ng/s320/VGIIIfig1.png" width="320" /></a></div>
<span style="text-align: left;"></span><br />
<a name='more'></a><span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">Lastly, the dual of a graph is dependent on the layout of the graph. If a graph has two different layouts, and these layouts cannot be stretched into each other (when drawn on a sphere) without edges crossing in the process, then the duals we get from each layout will be very different. These graphs will actually be topologically distinct graphs with different structures.</span><br />
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">All of this is to say that when we want to make statements about properties of a dual of a graph, we need to be very careful. We either need to pick a layout, prove that there is only one valid layout, or prove that whatever property we are interested in doesn't depend on the layout. Obviously, the first option is easiest if we can afford it.</span><br />
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">In the case of the Voroni graph in 2D, we can simply choose the layout that corresponds to each node of the graph being placed at it's corresponding point in 2-space. For the rest of this post, when I talk about the dual of the Voroni Graph, I'm referring to the dual of this layout of the Voroni Graph.</span><br />
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">What is the dual of the Voroni Graph? To answer that qualitatively, we're going to have to take sharp turn, click our heels, and talk about something that is, at first glance, completely different.</span><br />
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">Suppose we have a set of points in the plane, and we want to triangulate it, or create a set of triangles, each with vertexes in the set of points we started with. Furthermore, we want to make sure that our triangulation has some special properties. For instance, we want make sure that none of our triangles overlap. We'd like them all to be reasonably shaped, and not too long and pointy. We'd also like them to fill as much of the plane as possible.</span><br />
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">It's easy to verify that a triangulization doesn't overlap, but the other two conditions are less objective, and worse they sometimes contradict. Should we include a long triangle if there are no better options for filling space? To strike a compromise, we'll accept a triangle into our set if (and only if) no other points in out set lie within the triangle's circumcircle ( The circle that passes through all three vertices of the triangle ).</span><br />
<span style="text-align: left;"><br /></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKXGWjzD4dyB-4v4Vfqt4KF9e2BOD-vdZHFY7eWfY2PQXoNWFGSYrsyIjX6t0OluTZRI1L93y6HrLhWQj1J9xmqqhH-R8qcKG4VIbDfjPitqIu8vCq8R9IhSGJc4KcHEnMzaUGP7HmQA/s1600/VGIIIfig2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="155" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjKXGWjzD4dyB-4v4Vfqt4KF9e2BOD-vdZHFY7eWfY2PQXoNWFGSYrsyIjX6t0OluTZRI1L93y6HrLhWQj1J9xmqqhH-R8qcKG4VIbDfjPitqIu8vCq8R9IhSGJc4KcHEnMzaUGP7HmQA/s320/VGIIIfig2.png" width="320" /></a></div>
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">The set of all triangles formed form a set of points so the ate circumcircle of each triangle contains no extra points for the set is called the <span style="text-align: -webkit-auto;">Delaunay</span> Triangulation of the set. It (and it's generalizations to higher dimensions are) is a very important and interesting triangulation of the set, and hopefully we'll use it a lot going forward. In the mean time, however, I need to explain the relationship of the <span style="text-align: -webkit-auto;">Delaunay</span> Triangulation to the Voroni Graph.</span><br />
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">We can construct a graph (with an associated layout) from the <span style="text-align: -webkit-auto;">Delaunay</span> Triangulation as follows: Each triangle becomes a node located at the center of the triangle's circumsphere (aka it's circumcenter), and two nodes are linked if their triangles share an edge. I also find it useful to imagine a node located at infinity, and add edges from nodes that have fewer than three connections to this imaginary node. I'm going to refer to this whole construction as the <span style="text-align: -webkit-auto;">Delaunay</span> Graph, though I haven't seen this anywhere else (</span><span style="text-align: left;">To be honest, I haven't found much use for the <span style="text-align: -webkit-auto;">Delaunay</span> Graph yet, except as a conceptual tool for demonstrating how all this is related to the Voroni Graph).</span><br />
<span style="text-align: left;"><br /></span><br />
<span style="text-align: left;">Take a look at the conceptual sketch below (mostly to scale). As noted, in this case, the <span style="text-align: -webkit-auto;">Delaunay</span> Graph and the Voroni Graph are duals. In fact, looking closer, the drawing of the Voroni Diagram and the <span style="text-align: -webkit-auto;">Delaunay</span> Graph share a common structure, as do the <span style="text-align: -webkit-auto;">Delaunay</span> Triangulation and the Voroni Graph.</span><br />
<span style="text-align: left;"><br /></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh8fIo7R_dOht3m1ZwDozIXJ2r4NKgM9mJBgFPq1vtx7p3SLGqibofBFcklKeGBnGpJv2EX9db4NpAdfF8_8KTmnvoBIKy5x-xUu3u65ycCY0JPucTA-s2ZUQVVqmLm83DcjZAARQInGQ/s1600/VD5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh8fIo7R_dOht3m1ZwDozIXJ2r4NKgM9mJBgFPq1vtx7p3SLGqibofBFcklKeGBnGpJv2EX9db4NpAdfF8_8KTmnvoBIKy5x-xUu3u65ycCY0JPucTA-s2ZUQVVqmLm83DcjZAARQInGQ/s320/VD5.png" width="315" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div style="text-align: -webkit-auto;">
<span style="text-align: left;">Based of this, we might conjecture the following:</span></div>
<div style="text-align: -webkit-auto;">
</div>
<ol>
<li>The Voroni Graph and Delaunay Graph are duals.</li>
<li>Every Triangle in the Voroni Graph is in the Delaunay Triangulation (and vice versa).</li>
</ol>
<br />
<br />
<span style="text-align: left;">These are both very important ideas, and we'll be making heavy use of them (especially number 2) in future posts. But they are <u>not</u> completely true for Euclidian space, and it's important to understand when and why they can go wrong. For that, I'll introduce the following simple pathological example:</span><br />
<span style="text-align: left;"><br /></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiLENVh3XBDCP24merAFB3gdf0T37OyHWUEve_tioZxbp3HWZ-FEUBjXqYXAAz3yZ2LE-7Nf-8r2_-whWbKkFvHQ8ZJExyGVg4X8FdnUc1rTzY33_o1Oy36h6haFy-8vrirNFgMG6-n_A/s1600/VGIIIfig3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="117" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiLENVh3XBDCP24merAFB3gdf0T37OyHWUEve_tioZxbp3HWZ-FEUBjXqYXAAz3yZ2LE-7Nf-8r2_-whWbKkFvHQ8ZJExyGVg4X8FdnUc1rTzY33_o1Oy36h6haFy-8vrirNFgMG6-n_A/s320/VGIIIfig3.png" width="320" /></a></div>
<span style="text-align: left;"><span style="text-align: -webkit-auto;"><br /></span></span><br />
As you can see, the Voroni Graph for this set of points has four triangles as marked. Three of them complete the Delaunay Triangulation, but the fourth is NOT in the Delaunay Triangulation. Why does this happen (and can we expect it to happen often enough that we need to adjust for it)? My best answer, which I fully admit is a little handwavy, is that our statement about "Every Triangle in the Voroni Graph" is an inherently topological statement. It doesn't really take into account what space we're working in, and in this case, if we put these points through a stereographic projection and look a the result on a sphere, then yes, all four of these triangles are valid parts of the Delaunay triangulation.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXjbmtk3Adk5HBmf7ku3Nqudmtx2JH5pGAwe4qZmVP9wgG7V1d3dQZGpGiXVe8RGaIdlWh482kcNRsEwVVwSpUwFBsw7tfw_Bo-_TwXwfckY1eQW_jI7gxwovcmcytl8FSbBYQuGaLaw/s1600/VGIIIfig4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="194" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhXjbmtk3Adk5HBmf7ku3Nqudmtx2JH5pGAwe4qZmVP9wgG7V1d3dQZGpGiXVe8RGaIdlWh482kcNRsEwVVwSpUwFBsw7tfw_Bo-_TwXwfckY1eQW_jI7gxwovcmcytl8FSbBYQuGaLaw/s320/VGIIIfig4.png" width="320" /></a></div>
<br />
I'd love to stop here, and say that therefore this is something we can neglect because it'll only occur at most once on a dataset, and our datasets should be large enough that this one spurious triangle should get covered up pretty fast. Unfortunately, there's also the perfectly valid example given below.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhEA2UTl2fVGgiQWa9IvQ0MlxiDgVLg3bpGWk-UAFfHffiD7EveakRxD3Sd2T-XrhfqBtoZTX40RJ9nCgTCfDxgKt1bO5vc6d9cONZS2-Asy8HBySqg9xQjTexwDpLMTXiPFj6r07gehA/s1600/VGIIIfig5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="192" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhEA2UTl2fVGgiQWa9IvQ0MlxiDgVLg3bpGWk-UAFfHffiD7EveakRxD3Sd2T-XrhfqBtoZTX40RJ9nCgTCfDxgKt1bO5vc6d9cONZS2-Asy8HBySqg9xQjTexwDpLMTXiPFj6r07gehA/s320/VGIIIfig5.png" width="320" /></a></div>
<br />
I don't have an answer for this one, and I don't really know that there is one. The outer triangle I can explain away with the same stereographic projection trick, but there's just no excuse for the one in the middle in two dimensions (Unless of course, you've got a better grasp on this than me, in which case, you should leave a comment!). Worse, this counterexample can be embedded in any otherwise well behaved set of points for an instant spurious triangle.<br />
<br />
At the end of the day, however, I'm going to claim that this kind of thing doesn't seem to be very common. If I throw down a set of random points, I've haven't yet seen it come up of it's own accord. In the long run, I think the jury will be out until I've written a program that can make a few million large point sets and search for these sorts of things. And in that vein, we'll be discussing how to implement such a program next time.Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-58563417582720167252012-04-10T10:24:00.002-04:002012-06-08T12:45:11.595-04:00Voroni Diagrams and Graphs II: Some Applications of the Voroni Graph.<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><div style="text-align: left;">
In this post, I'll further discuss the concept of the Voroni graph we talked about last time, and talk about some uses. We'll see more uses in the next post, where I'll talk a bit about a related graph.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Supposing we know the Voroni Graph of a set of points, what can we do with it?</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
First, we can use it to check if a point p is in the Voroni cell of some point in our set q. If we find all the neighbors of q ( points that have an edge to q in the Voroni Graph ) we only have to check to make sure that p is closer to q than any of these points, since we already know that these neighbors alone are sufficient to define the cell of q.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Let's briefly look at how much of an improvement this is over a normal check. Let's assume we have a set of n randomly distributed points, and n is very large (AKA we can neglect the effects of the outermost border of the points, and we're not going to get anything unusual in our graph).</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
If we have to check each point to see if p is closest to q, then we'll take O(n) time. This isn't bad, but if we assume we have access to the Voroni graph, we can do much better.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
We need to find how many neighbors a typical Voroni diagram has.We know that the Voroni graph is planar, so it will obey Euler's formula ( V − E + F = 2 ). If the points are fairly random, then almost all of the "faces" of the graph will be triangles ( A non triangular face, we'll see later, implies that at least four of the points lie on a single circle, which is in general not true. ). Because of this F = 2E / 3 ( each triangle is bounded by three edges, and each edge divides two triangles ).</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: center;">
V - E + (2/3) E = 2</div>
<div style="text-align: center;">
V - 2 = (1/3) E</div>
<div style="text-align: center;">
E/V = 3 - 6 / V<br />
2E/V = 6 - 12 / V</div>
<div style="text-align: center;">
<br /></div>
<div style="text-align: left;">
The quantity 2E/V represents the average number of neighbors of each vertex (we double the number of edges so that both ends can count it). Thus, as the number of vertices becomes large, each vertex will have on average only 6 neighbors. Thus, if we can use the Voroni Graph, we can check our point in only O(1) time!</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
It's worth noting of course, that this isn't quite as good as it seems. After all, we still have to compute the Voroni Graph, and we'll need to store it in such a way as to allow ourselves to look up a given vertex quickly. Still, it's an achievement, and it lets us know that if we're going to be checking lots of points, we'd be better off investing our time in making the Voroni graph rather than brute forcing the problem.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Even better, because p is in the cell of q if and only if it is closer to q than q's neighbors, it is also painless to find out which point is closest to p. We simply pick a starting point q<sub>1</sub>, and check if that point is closest to p. If it is not, we call the neighbor of q<sub>1</sub> q<sub>2</sub>, and check if it is closest. This continues until we find that p is closest to q<sub>n</sub> relative to its neighbors Because of the nice properties of the Voroni graph, we can say that q<sub>n</sub> will be the point in our point set which is closest to p. In other words, having the Voroni graph lets us do a greedy search to find the Voroni cell to which a point belongs.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
I would love to analyse the run-time of this particular algorithm, given a large set of points and a randomly chosen starting point, but I must confess I am not clever enough to put down any of my thoughts on paper at this point. I'll continue to think on it, but my money is on O( n<sup>1/2</sup> ) for 2D ( and more generally O( n<sup>1/d </sup>) for dimension d ). I think this is how the average euclidean distance between two randomly selected points scales as the number of points increases.<br />
<br />
In any case, it is a great improvement over the naive approach, which would require us to check the distance to every point, and thus would have O( n ) run-time.<br />
<br />
That's it for this post. I've got two more queued up and ready to go as soon as I have time to edit them and add figures, so expect more on this topic soon.</div>
</td></tr>
</tbody></table>
<br />Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-86536486197707493332012-03-17T12:27:00.003-04:002012-03-17T14:21:21.353-04:00The Hough Transform I: Finding LinesI've made reference to the Hough Transform in several previous posts, but I haven't ever done posts on what the transform is in a general sense, and how I've used it (and tried to improve it) in the past. In this series of posts, I'll try to rectify that.<br />
<div>
<br />
The most basic implementation of the Hough transform is used to find lines in an edge image like the one below. In this post I'll walk through the basic process of using the Hough transform to find lines in this image.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://upload.wikimedia.org/wikipedia/commons/9/93/Valve_monochrome_canny_(6).PNG" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="240" src="http://upload.wikimedia.org/wikipedia/commons/9/93/Valve_monochrome_canny_(6).PNG" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">An image of machinery with edge detection applied. This image would be a good candidate for further processing with the Hough transform. (Source: Wikipedia)</td></tr>
</tbody></table>
Underlying the Hough transform is the idea that each pixel in an an image tells us something about the chances of there being certain lines in the entire image. If we have a pixel at point p, then it would make sense to look at all the lines that pass through p, and see if any of them happen to pass very close many other points in the image. If a particular line through p passes close to an unusual number of points, then it's a pretty reasonable to assume that this line constitutes an actual feature in the image.<br />
<a name='more'></a><br />
<div>
Naively, we might imagine making this process directly into an algorithm. Take each point in turn, and search through the lines that pass through that point, looking for ones that pass through an unusually high number of points. This would probably work, but I doubt it would work particularly well.<br />
<br />
Even if our algorithm works perfectly, accepting all of the best lines for each point and nothing else, we'll be left with many duplicate lines, all of which will likely be subtly different due to rounding error, randomness in the image, and the fact that pixels are discrete. Clustering these lines into a reasonable number of representatives will be costly and potentially complicated.<br />
<br />
The idea that we can reduce the number of lines we have to consider by using points from our image is solid, but clearly focusing on one point at a time makes us do a lot of duplicate work. Instead, we should try to focus on all the points at once, letting each point cast some sort of vote for lines that pass through it. We'll have a sort of arbiter that will collect all the votes, then, after the votes have been cast, we'll search over the space of lines for particularly dense clusters of votes, and choose a line to characterize each cluster. This is the idea underlying the Hough transform.<br />
<br />
To actually formalize and use the Hough transform, we need to flesh out how the arbiter (which we're going to call the Accumulator from here on out) stores the set of all possible lines, and how it determines the most popular of these lines.<br />
<br />
First a brief refresher on points.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhWc9XFwHhWhsmhLivzH2BYSESsbwdmn1pqGjp87H5QNzjk23wWQ12czwD3zh1wFlIcWwut8kddW0v3H8BFNCRUKDPl1JR7NtK4xUbSHlw0SNaHkZxnoAcztYHCgPDcj2q8UyrGCo78vg/s1600/HT1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="252" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhWc9XFwHhWhsmhLivzH2BYSESsbwdmn1pqGjp87H5QNzjk23wWQ12czwD3zh1wFlIcWwut8kddW0v3H8BFNCRUKDPl1JR7NtK4xUbSHlw0SNaHkZxnoAcztYHCgPDcj2q8UyrGCo78vg/s320/HT1.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Different ways to represent a point p in <b>R<sup>2</sup></b>. </td></tr>
</tbody></table>
There are two major ways to represent an arbitrary point in <b>R<sup>2</sup></b>. The Hough transform as it is simplest to implement uses both. We could represent a point as a set of values ( x, y ), where we first move x units in one direction, then y units perpendicularly (or vice versa), or we could describe it as a set of values ( rho, theta ) where rho is the distance from the origin to the point, and theta is the angle from our point to the origin and out the x axis measured clockwise. For the purposes of actual implementation, I'll stick to the convention that theta is between -pi and pi.<br />
<br />
In terms of implementation, it can be tricky to make an elegant data structure which can deal with both of these cases. I like to use inheritance ( or in java, an interface ) to give my self two types of points which can be converted into each other when needed.<br />
<br />
It's also worth keeping in mind that most systems for representing images use coordinate systems that have opposite chirality from the systems I've drawn in my figures. This turns out not to be an issue so long as we're consistent about it. Still, if you implement your own version of the transform, it's easy to mess up.<br />
<br />
Next we need to think about how to concisely and uniquely represent lines. I claim that the space of all lines in <b>R<sup>2</sup></b> is itself two dimensional. While it's not a proof, one way to reason this out is as follows: we can represent any line with two points for a total of 4 parameters. Two of these parameters, however, can be thought of as representing the positions of the points we chose on the line. Since we want to represent a line independent of our reference points, we ought to be able to neglect these parameters somehow.<br />
<br />
There is in fact such a way. It is often useful to represent lines by the point on that line closest to to some reference point ( for the Hough transform, we'll typically take this point to be the origin ). This is a really nice way to do things with a single flaw: it doesn't leave us with a way to uniquely represent lines that pass through our reference point. For our purposes, I'm going to gloss over this and assume that there are no lines that pass through the origin. If you're worried that there might be, it's pretty easy to just check for these lines as a last step, since they all by definition pass through the origin.<br />
<br />
In the figure below, I've drawn a sampling of lines through a specific point, and marked on each line the point closest to the origin.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQM0fmk4q5lc_X4Tg1kMxZAF3nd80VlWP04ulfidxhKX8NpLSGttDVOf3ibWIL_fr4mwlfIfilB6DcRDSKoPScCyVTnsjsN1lV_-liF31V9EHzQSYF0dJBz0XSZ_lc3nJ7N-dJoudDlw/s1600/HT3.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhQM0fmk4q5lc_X4Tg1kMxZAF3nd80VlWP04ulfidxhKX8NpLSGttDVOf3ibWIL_fr4mwlfIfilB6DcRDSKoPScCyVTnsjsN1lV_-liF31V9EHzQSYF0dJBz0XSZ_lc3nJ7N-dJoudDlw/s320/HT3.png" width="316" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Sample lines through a point (filled) and<br />
the points on those lines closest to the origin (open).</td></tr>
</tbody></table>
Stare at the image above for a moment, and you'll notice something funny. The points closest to the origin on all of these lines look like they might form a circle. This is in fact the case, as is shown in the image below. If we take a circle which has a diameter from the origin to any point p of choice, the angle between the origin, any point q ( misnamed [L] in the figure ) on that circle (except of course the origin or p) will, and p will be a right angle by basic geometry. This turns out to be the necessary and sufficient condition to say that the q represents a line that passes through p.</div>
<div>
<br /></div>
<div>
In fact, if you think about it for a while, you may be able to see that this circle (with the origin removed) represents all the points that represent lines that pass through p. There are multiple ways I know of to show this, so I'm going to leave it as an exercise to the reader.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3eOKWP8Z7IrJ5_Qn_W_jJ86PqkmC0shEI6ofNTtDkaJ7WZWIjJniVTnTQas0wbvCDBWjBTTPefqZeKslbY83aACH_rUQUWlV5wuHjRXX19rhyJDOS39qn_BkdLM0fYFOTOuwRwhqUjg/s1600/HT2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="265" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3eOKWP8Z7IrJ5_Qn_W_jJ86PqkmC0shEI6ofNTtDkaJ7WZWIjJniVTnTQas0wbvCDBWjBTTPefqZeKslbY83aACH_rUQUWlV5wuHjRXX19rhyJDOS39qn_BkdLM0fYFOTOuwRwhqUjg/s320/HT2.png" width="320" /></a></td></tr>
<tr><td class="tr-caption">Graphical depiction of the set of points that are the<br />
closest points to the origin on lines that pass through<br />
p. note that the Origin is not actually part of<br />
this set, although it does lie on the circle.</td></tr>
</tbody></table>
The only tricky bit left is the exact implementation of the accumulator. Here, there are lots of choices, the the simplest it arguably as follows: produce a two dimensional set of bins, one set for theta, the other for rho (we assume that rho <= some rho_max, which turns out to be quite reasonable for images, since images are finite. ). As we look at each point, we'll chose a representative set of lines spaced equally along the circle. We'll put each of these lines into the bin which contains the particular value of r and theta for the point that represents that line.</div>
<div>
<br /></div>
<div>
Once all the points have had their lines tallied, we can find the bins which are most populated (checking to make sure that we have local maxima to avoid duplication), then return the median rho theta value for each as a list of lines. These lines will correspond to the lines in our image, and we'll be done!</div>
<div>
<br />
I have some code to go with this post, which should be up as soon as I clean it up and document it. In the mean time, though, I'm going to put this post up.</div>Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-43231299430091203802012-03-16T15:58:00.002-04:002012-03-16T15:58:56.687-04:00MIT Library Scanning......turns out to be a great way to scan figures. It's a ton faster than using my own scanner, and the resolution isn't too much worse. I'm writing a few math-oriented and cs-oriented posts with figures right now, and the book scanner means I can just box figures in my notebooks and use Gimp / Picasa Web Albums to crop things down and clear up the colors. It's a much faster pipeline than what I had before, and I'll hopefully make use of it to put lots of pretty figures in my posts.Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-88769063361197088632012-03-11T00:05:00.004-05:002012-03-16T17:42:37.687-04:00Voroni Diagrams and Graphs I: IntroductionSuppose we have a set of points { p<sub>0</sub>, p<sub>1</sub>, ..., p<sub>n</sub> }, each of which lives in <b>R<sup>2</sup></b>. A Voroni Diagram is a partitioning <b>R<sup>2</sup></b> into regions { [p<sub>0</sub>], [p<sub>1</sub>], ..., [p<sub>n</sub>] } so that any point q in [p<sub>i</sub>] is at least as close to p<sub>i</sub> as any other p<sub>j</sub>. Note that, for most points, this should mean that q is strictly closest to p<sub>i</sub>, but we're also going to include the boundaries of these regions, so they'll all be closed sets ( If it were to strike your fancy, you could also use open sets. We'll use the closed property a bit later on, but it's mostly personal preference. ).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgfaVs9jseutaEkc6oCwhoIExgGdzYVuXJTiiLveCLeGEGymW7J6JIT3LikOSd5E36yRcGLKVHwX_Po2v38Us1RvpxeuUMyyWIUBrR9PTIqlF_euG363j8MhpQk2UY11JtZXLHnmE4qLQ/s1600/IMAG0104.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="276" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgfaVs9jseutaEkc6oCwhoIExgGdzYVuXJTiiLveCLeGEGymW7J6JIT3LikOSd5E36yRcGLKVHwX_Po2v38Us1RvpxeuUMyyWIUBrR9PTIqlF_euG363j8MhpQk2UY11JtZXLHnmE4qLQ/s320/IMAG0104.jpg" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br />
This is all a perfectly good definition of what Voroni Diagrams are, but it doesn't explain how to find them in practical situations or what they're useful for. In this post, I'll explain a basic approach for finding a Voroni Diagram, and present an (inefficient) algorithm I made up to find what I call the Voroni graph: a graph whose vertices are the { p<sub>0</sub>, p<sub>1</sub>, ..., p<sub>n</sub> }, and whose structure describes the diagram (and provides a quick way to check if q is in a given [p<sub>i</sub>], among other things ).<br />
<br />
<br />
<a name='more'></a>To actually find the Voroni Diagram, we'll start by thinking about the boundaries of [p<sub>i</sub>], a single cell of the diagram.<br />
<br />
Imagine we only have two points: p<sub>i</sub> and p<sub>j</sub>. In this case, the boundary between [p<sub>i</sub>] and [p<span style="font-size: x-small;">j</span>] is the perpendicular bisector of the segment between p<sub>i</sub> and p<sub>j</sub>. Why? Each point on the bisector is equidistant from the two points. By our definitions, that means that each one of these points belongs in both cells. Furthermore, if we move off this line, then we know that we'll be strictly closer to one point or the either. If we move off the bisector in the direction of p<sub>i</sub>, then we'll be strictly closer to p<sub>i</sub> and vice versa.<br />
<br />
It follows that [p<sub>i</sub>] is exactly the closed half plane bounded by the perpendicular bisector between p<sub>i</sub> and p<sub>j</sub>. It's worth noting at this point that a very convenient way to store this line is just the point on the line closest to p<sub>i</sub>: (p<sub>i</sub> + p<sub>j</sub>)/2.<br />
<br />
If a point q is as close to p<sub>i </sub>as any other p, it must be individually as close to p<sub>i</sub> as any other specific p<sub>j</sub>. The converse also holds. While this may seem obvious, it's very important, because it means we can find [p<sub>i</sub>] by intersecting all the half planes we obtain by considering only p<sub>i</sub> and each p<sub>j</sub> individually. We might store the resulting region as the as the series of points { (p<sub>i</sub> + p<sub>0</sub>)/2, (p<sub>i</sub> + p<span style="font-size: x-small;">1</span>)/2, ..., (p<sub>i</sub> + p<span style="font-size: x-small;">n</span>)/2 }, the points on the boundary of each half plane closest to p<sub>i</sub>.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-ojtw8lVZt0DgCl0OgzVMWm07n8jARBYCKcByf4Ss4zOiF5MUij4OSjXICocv_Byxvo1jXix2uNis9cQt3I5S12VVoiX3Lt0AVhYyQWe7ZF1-pD2r4DWS8mID3-uCdbOCkjQ8lbo0SA/s1600/IMAG0107.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="216" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj-ojtw8lVZt0DgCl0OgzVMWm07n8jARBYCKcByf4Ss4zOiF5MUij4OSjXICocv_Byxvo1jXix2uNis9cQt3I5S12VVoiX3Lt0AVhYyQWe7ZF1-pD2r4DWS8mID3-uCdbOCkjQ8lbo0SA/s320/IMAG0107.jpg" width="320" /></a></div>
<br />
This set of points functions as a complete description of [p<sub>i</sub>], but it's not the smallest description. To get that, we'll need to check that we don't have unused or redundant borders. If one closest point is not in the (open) half plane of both of two other points, then there's no way it can effect the final shape, so we can discard it. If we use this process to remove redundant points, then we'll have a compact description of [p<sub>i</sub>].<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj5O-qe4U18dGvPaBONqRrP_MVDlYdTq3S37sxzJwJcIAHAwdkaM1vLd8lrg5ypt13ROaipSErhj9Ftkh-ex9hyphenhyphenw6mqillgGE2_V5XlUcYwxaWUNWr5WK0VK1cGe8n8qauI4Iq71WysXw/s1600/IMAG0105.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj5O-qe4U18dGvPaBONqRrP_MVDlYdTq3S37sxzJwJcIAHAwdkaM1vLd8lrg5ypt13ROaipSErhj9Ftkh-ex9hyphenhyphenw6mqillgGE2_V5XlUcYwxaWUNWr5WK0VK1cGe8n8qauI4Iq71WysXw/s320/IMAG0105.jpg" width="252" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhLf6lWRzOaI5L056IeFBRrKw6Yjjt6bRd7x5yMV6QmlRt3bgAYMWFQmOh3ZzW2dNw1VUfsltfwBkgh09Wlk4DrN8zvrzY6vRPGAQN6xIkgcNrmWU-15_Q651OwGpTcc0x_i8nTiIBpTA/s1600/IMAG0103.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhLf6lWRzOaI5L056IeFBRrKw6Yjjt6bRd7x5yMV6QmlRt3bgAYMWFQmOh3ZzW2dNw1VUfsltfwBkgh09Wlk4DrN8zvrzY6vRPGAQN6xIkgcNrmWU-15_Q651OwGpTcc0x_i8nTiIBpTA/s320/IMAG0103.jpg" width="278" /></a></div>
<br />
<br />
Once we have a method for finding this minimal description of each [p<sub>i</sub>], it's pretty simple to define the Voroni Graph. The nodes of this undirected graph are { p<sub>0</sub>, p<sub>1</sub>, ..., p<sub>n</sub> }, and there is an edge between p<sub>i</sub> and p<sub>j</sub> if and only if (p<sub>i</sub> + p<span style="font-size: x-small;">j</span>)/2 is in the description of [p<sub>i</sub>].<br />
<br />
Equivalently, we could also say that there is an edge between p<sub>i</sub> and p<sub>j</sub> if and only if there are at least two distinct points q and r each in both of [p<sub>i</sub>] and [p<sub>j</sub>], since this is another way to say that [p<sub>i</sub>] and [p<sub>j</sub>] share a border. There's a little bit of math involved in showing that having two points really is the same as sharing a line segment border. If you're interested or skeptical, try proving that Voroni regions are all convex.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi3or6WXMYzKryBBqGwuJ57shnc8YMl9FxwW5bFPEHQFb-lcIVK-CVur0jSAgpJhRa6K05HCme0GcH9mH7vEHacdlu558qydFnkytQOHHpiZB4jJ3w-Ji2DrT2jHQwfZoc1aJwjjdpoLA/s1600/IMAG0106.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="248" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi3or6WXMYzKryBBqGwuJ57shnc8YMl9FxwW5bFPEHQFb-lcIVK-CVur0jSAgpJhRa6K05HCme0GcH9mH7vEHacdlu558qydFnkytQOHHpiZB4jJ3w-Ji2DrT2jHQwfZoc1aJwjjdpoLA/s320/IMAG0106.jpg" width="320" /></a></div>
<br />
<br />
That's it! This is a functional definition of the Voroni Graph both mathematically and practically speaking. Later on, we're refine our process for finding this graph, but the basic idea is complete.<br />
<br />
I'll touch this post up with pictures some time soon. In the next two posts on this subject, I'll first describe some more math surrounding the Voroni Graph. Finally, we'll revisit the process of finding a Voroni Graph, and generalize it to <b>R<sup>n </sup></b>and beyond.Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-78797437093693495052012-02-12T23:47:00.000-05:002012-03-10T14:58:23.325-05:00Quaternions I: OverviewWhat are quaternions? Let's start with what quaternions once were: an attempt to extend Complex numbers to three dimensions.<br />
<br />
Back when <a href="http://en.wikipedia.org/wiki/Complex_number#Complex_plane">the geometric interpretation of complex numbers</a> as a plane was reasonably fresh, <a href="http://en.wikipedia.org/wiki/William_Rowan_Hamilton">Sir William Hamilton</a> became interested in finding a system of algebra that would allow him to express three dimensional space in the same way. To do this, Hamilton needed a way to add and multiply points in 3 dimensional space together.<br />
<br />
Addition came easy. Picking some arbitrary origin and axes <i>1</i>, <b><i>i</i></b>, and <b><i>j</i></b> to work with, Hamilton just defined <i>(a + b<b>i</b> +c<b>j</b>) + (d + e<b>i</b> +f<b>j</b> ) = ( a + d ) + ( b + e )<b>i</b> + ( c + f )<b>j</b></i>.<br />
<br />
Multiplication, though, was a problem. Assuming that these new quantities were distributive, Hamilton needed to define <b><i>ij</i></b> in such a way that various other properties still held. Despite his best efforts, he couldn't do it.<br />
<a name='more'></a><br />
Still, Hamilton found a way forward. By adding <i>a fourth axis</i>, k, Hamilton could define that <i><b>i</b>^2 = <b>j</b>^2 = <b>k</b>^2 = <b>ijk</b> = -1</i> and everything worked nicely. In Hamilton's view, he'd found <u>the</u> best way to represent 3D space. He called the new construct a quaternion and spent the rest of his life promoting their use in physics and chemistry.<br />
<br />
Eventually, though, quaternions dropped out of style. They were elegant in some situations, but unintuitive and clumsy in others, and the vector math we have today often suited physicists better. For the better part of a century, quaternions went unused outside of some mathematics.<br />
<br />
Clearly, though, quaternions are useful for something, or I wouldn't be writing about them. To understand why they're so neat, though, we need to change tack and talk about something else: gimbals.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://upload.wikimedia.org/wikipedia/commons/5/5a/Gimbal_3_axes_rotation.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="http://upload.wikimedia.org/wikipedia/commons/5/5a/Gimbal_3_axes_rotation.gif" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Spinning Gimbals, courtesy of Wikipedia</td></tr>
</tbody></table>
A gimbals are a set of rings attached by pivots. Usually, as in the image above, there are three rings: an outer gimbal, which can rotate freely around, for instance, vertical with respect to the enviroment, and two inner gimbals, each is mounted at right angles with respect to the axis of the last gimbal.<br />
<br />
The purpose of all this is generally to allow some sort of equipment (often a flywheel, whose inertia will keep it level) to rotate freely. If we want to think about the state of the gimbal mathematically, we can assign one angle to each set of joints, for a total of three numbers. This makes sense, of course, because we're trying to capture a three dimensional space (the surface of a sphere accounts for two dimensions, plus we need to be able to rotate around each point we choose).<br />
<br />
Mathematically, we also might like to be able to think of rotations as something you can combine, one after another. In order to do this, we have so called Euler Angles: 3x3 matrices which we can combine through matrix multiplication. We also can apply this matrix to a three dimensional vector.<br />
As you'll see later in this article<br />
<br />
In most situations, this whole setup works nicely, and we're done. There is one time when it fails, however. Going back to the gimbals, it's possible for two of the axes to line up, constraining the rotation! In other words, while the gimbal usually provides three degrees of freedom, at two specific points, it only provides two. Euler Angles have the same problem.<br />
<br />
This is a big enough problem that there is a mechanical solution for actual gimbals: add a fourth constrained ring. As long as you always have at least three non-parallel axes, you can rotate. As long as the fourth gimbal is always in position to take over if two other rings line up, the local space of movements will be three dimensional.<br />
<br />
Now if we wanted to represent the gimbals mathematically, we'd have four numbers to worry about, but there would be a constraint on at least one of them. We might like to imagine that there is some constraint will be sufficiently strong to mean that given three of these numbers, we could find the fourth uniquely. In fact there is.<br />
<br />
Let's back up for a second. If we're willing to accept that our experiments with gimbals will roughly hold, we've found that in order to properly express rotations, we're going to need more than three just some subset of normal three dimensional space. Specifically, we'll need some kind of three dimensional surface in four dimensional space to properly express rotations in all cases.<br />
<br />
Now, where have we seen a four dimensional space before? That's right: quaternions are exactly what we're looking for. Specifically, the unit quaternions, the set of quaternions <i>a + b<b>i</b> + c<b>j</b> + d<b>k</b></i> which satisfy<i> a^2 + b^2 + c^2 + d^2 = 1</i>, are useful.<br />
<br />
Imagine we want to rotate 3-D space about an unit axis <i><b>v</b> = b<b>i</b> + c<b>j</b> + d<b>k</b></i> ( <i>b^2 + c^2 + d^2 = 1</i> ) by an angle <span style="background-color: white; font-family: sans-serif; font-size: 13px; line-height: 19px;"><i>θ</i></span>. Let <i>q = cos( <span class="Apple-style-span" style="background-color: white; font-family: sans-serif; font-size: 12px; line-height: 18px;">θ</span> / 2 ) + sin( <span class="Apple-style-span" style="background-color: white; font-family: sans-serif; font-size: 11px; line-height: 17px;">θ</span> / 2 )<b>v</b></i>, and let <i>q^-1 = cos( </i><span class="Apple-style-span" style="background-color: white; font-family: sans-serif; font-size: 12px; font-style: italic; line-height: 18px;">θ</span><i> / 2 ) - sin( </i><span class="Apple-style-span" style="background-color: white; font-family: sans-serif; font-size: 11px; font-style: italic; line-height: 17px;">θ</span><i> / 2 )</i><b style="font-style: italic;">v</b>. Then, if we have an arbitrary vector <i style="font-weight: bold;">u</i>, the rotation applied to <i><b>u</b></i> will give us the vector <i>q<b>u</b>q^-1</i>! That's it! The great thing about this method is that everything is uniform. There are no singular points, no weird exceptions, and combining the rotation <i>q</i> followed by the rotation <i>p</i> into a single rotation is as simple as finding <i>pq</i>. Nice, huh?<br />
<br />
If you want to understand exactly why that works, <a href="http://www.geometrictools.com/Documentation/Quaternions.pdf">you should look here</a>. I'm not going to go into detail because I intend this just to be a functional primer.<br />
<br />
Also, once I get it working, I may post some C++ code with python bindings( I'm in the process of porting various things ).Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-24340545654330425332011-11-19T13:04:00.001-05:002011-11-19T13:18:50.407-05:00SPLASH!These are all the materials I used/planned to use in class. I'll also put some links below for topics/sites I find interesting. Hope it helps! If you leave comments, I can try to get back to you and direct you to resources.<br />
Happy Coding!<br />
~Will<br />
<br />
Where to go in order to...<br />
<br />
<ul>
<li><a href="http://python.org/">Install Python</a></li>
<li><a href="http://notepad-plus-plus.org/">Install Notepad++</a> (A good text editor for working with python on windows. On Linux/Mac, you should be able to use whatever you have on hand.)</li>
<li><a href="http://greenteapress.com/thinkpython/thinkpython.html">Learn Python</a></li>
<li><a href="http://projecteuler.net/">Do fun problems!</a></li>
</ul>
<div>
Stuff I wrote for the class (I'm planning on teaching this class again next year, so I may write more worksheets...):</div>
<div>
<ul>
<li><a href="http://dl.dropbox.com/u/34006843/Ninjinuity/Article_Files/SPLASH/Expressing%20the%20%28almost%29%20Infinite.pdf">Expressing the (almost) Infinite</a></li>
<li><a href="http://dl.dropbox.com/u/34006843/Ninjinuity/Article_Files/SPLASH/Project%20Euler%20Problems%20.pdf">Project Euler Problems</a></li>
</ul>
<div>
Neat Topics</div>
</div>
<div>
<ul>
<li><a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes</a></li>
<li><a href="http://en.wikipedia.org/wiki/Collatz_conjecture">http://en.wikipedia.org/wiki/Collatz_conjecture</a></li>
<li><a href="http://en.wikipedia.org/wiki/Genetic_algorithm">http://en.wikipedia.org/wiki/Genetic_algorithm</a></li>
<li>and more...</li>
</ul>
</div>Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-17314015817719150492011-10-14T17:35:00.000-04:002011-10-14T17:46:56.546-04:00Imaging Exoplanets: Out of this world pictures<a href="http://spacetelescope.org/static/archives/images/screen/heic0821a.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="213" src="http://spacetelescope.org/static/archives/images/screen/heic0821a.jpg" width="320" /></a> Back in 2008, the image at left was plastered across the front page of many science related publications. For the first time, scientists had directly imaged an exoplanet (a planet which orbits another star) with visible light.<br />
Exoplanets themselves were nothing new. In late 2008, <a href="http://web.archive.org/web/20081218012250/http://exoplanet.eu/catalog.php">333 exoplanet canidates were known</a>, and 8 of those had been detected using direct imaging. In fact, Fomalhaut b itself, the planet pictured, was actually not truly a new discovery. <a href="http://iopscience.iop.org/0067-0049/154/1/458">Since 2004 scientists had been reasonably confident it existed because of the sharp inner edge of the band of dust around the star Formalhaut.</a> The thought was that a large planet (namely Fomalhaut b) was sweeping the material from the inside of the band into itself.<br />
<a name='more'></a><br />
Formalhaut b was an excellent choice for direct imaging precisely because it was large and it was clear roughly where it was. When <a href="http://www.sciencemag.org/content/322/5906/1345">the 2008 analysis of data from the Hubble space telescope</a> was published by Paul Kalas, it was greeted with plenty of excitement, but not much surprise.<br />
Since 2008, scientific consensus on Fomalhaut b has slowly disintegrated. The "planet" is much brighter than expected, which, according to models of planet formation, should mean it is very hot (and should radiate infrared light). Despite this, <a href="http://adsabs.harvard.edu/abs/2009ApJ...700.1647M">Fomalhaut b doesn't seem to show up in the infrared spectrum at all.</a><br />
As of last month, there's another puzzling data point. <a href="http://www.nature.com/news/2011/110923/full/news.2011.555.html">A third image taken recently shows that Formalhaut b's orbit isn't as textbook-perfect it seemed back in 2008.</a> If the new data is correct, the exo-planet would need to veer into the dust once every orbit. This means that it would be actively reshaping the cloud, which is entirely inconsistent with previous results. This is leading some scientists to doubt that Fomalhaut b is a planet at all, though it isn't clear what real alternatives exist.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://apod.nasa.gov/apod/image/0811/hr8799_keck.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="320" src="http://apod.nasa.gov/apod/image/0811/hr8799_keck.jpg" width="317" /></a></div>
Does all this mean we've never imaged an exoplanet before? To the contrary, <a href="http://exoplanet.eu/catalog-imaging.php">we've imaged 24 other planets directly</a>. Notable among these is HR 8788. Why is this particular system notable? There are two reasons. Also imaged in 2008 ( in infrared, rather than visible light), HR 8788 is to date the only star where we have imaged an entire planetary system.<br />
In addition, in 1998, before any exoplanets had been detected, HR 8788 was imaged by Hubble in an attempt to find exoplanets. At the time, the study found nothing, but only because researchers didn't have the correct techniques to pick the exoplanets out of the data!<br />
Recently, in a superb demonstration of how much astronomy had advanced over the last decade, <a href="http://hubblesite.org/newscenter/archive/releases/2011/29/image/a/">astronomers went back to that 1998 data and used modern techniques to analyse the images</a>. Lo and behold, out come the same three exoplanets (see below).<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://imgsrc.hubblesite.org/hu/db/images/hs-2011-29-a-print.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="163" src="http://imgsrc.hubblesite.org/hu/db/images/hs-2011-29-a-print.jpg" width="400" /></a></div>
<div style="text-align: left;">
One can only imagine the data magic we'll be able to pull off in another 13 years of exoplanetary research.</div>Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-52656214848126588812011-09-25T21:58:00.000-04:002011-10-14T20:20:21.348-04:00Of mice, men, and microRNAs.<div>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/V9fAz3zsQhI?feature=player_embedded' frameborder='0'></iframe></div>
Although <a href="http://www.nature.com/nature/focus/crick/pdf/crick227.pdf">RNA is most famous for acting as an intermediate between DNA and Protein</a>, we've come to understand that RNA's role in the cell goes far further in recent years. Some kinds of RNA, like miRNAs, actually change the balances of proteins made, leading to a wide variety of effects.<br />
What exactly is a miRNA? miRNAs or microRNAs are tiny segments of RNA. Where <a href="http://www.springerlink.com/content/qx15172307903468/">most RNA segments are about 1,400 nucleotides long</a>, <a href="http://www.sigmaaldrich.com/life-science/functional-genomics-and-rnai/mirna/learning-center/mirna-introduction.html">miRNAs are typically only about 22 nucleotides</a> long. While miRNAs are sometimes written out by themselves on DNA (as in the video above), it's more common to see miRNAs created as a byproduct of the creation of other kinds of RNA. Unlike many other types of RNA, miRNAs don't encode for proteins or assist in their transcription of RNAs to protein. Instead, miRNAs prevent proteins from being made from mRNAs by latching onto them before they can be transcribed. In the past few years, miRNAs have been <a href="http://www.ncbi.nlm.nih.gov/pubmed/19264914">implicated in certain types of cancer</a>, and <a href="http://www.nature.com/nbt/journal/v26/n4/full/nbt0408-400.html">been used as biomarkers to help detect and diagnose diseases</a>.<br />
<a href="http://www.blogger.com/blogger.g?blogID=8175863459692085" name="more"></a> All of this is very exciting on its own, but more exciting still is <a href="http://www.nature.com/cr/journal/vaop/ncurrent/full/cr2011158a.html">a paper recently published in Nature Cell Research</a> which suggests that miRNAs can actually travel from material in the digestive system of an organisms you eat into its bloodstream. Scientists at Nanjing University, China found a certain miRNA from rice, called MIR168a, in the bloodstreams of both humans and mice. By varying the diets of lab mice, they were subsequently able to show that the miRNAs found in mouse blood were being ingested.<br />
This alone is an important discovery, but the researchers further "hypothesized that [plant miRNAs] may play a role in regulating the functions of mammalian cells and organs". Looking through the known sequences of mouse and human mRNAs, they identified about 50 proteins which MIR168a was likely to interfere with, including LDLRAP1, a gene that codes for a liver protein in both humans and mice. By exposing a certain type of liver cell (HepG2) to increased miRNAs, they determined that "Plant MIR168a...significantly decreased the LDLRAP1 protein level in the recipient HepG2 cells" while LDLRAP1 mRNA levels remained unaffected. In other words, the miRNA was preventing the transcription of the LDLRAP1 mRNA, as expected.<br />
Why care about this result? It further clouds the waters regarding the role environment plays gene expression, an area of much of interest in biology right now. In addition, if miRNA uptake turns out to be common (or at least easy to induce) in humans then it could lead to whole new classes of oral drugs that target the expression of specific proteins.</div>Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-75487133100650914182011-09-24T21:31:00.000-04:002011-09-25T13:06:19.384-04:00E≈Mc^2? If there's one result worth posting about from this week, it is the now famous (and in some circles infamous) exchange of neutrinos between CERN and OPERA, two European physics laboratories. Neutrinos are pretty cool as is, but what's really of interest here is what the neutrinos (muon-neutrinos, to be exact) appear to be doing on their trip from their creation at CERN to their detection at OPERA. They're arriving ever so slightly early: 60 nanoseconds early to be precise. For reference, quick calculation shows that light only travels 24 meters (just under 80 feet) in that time.<br />
How fast light travels is actually exactly what's at issue here; the neutrinos seem to be arriving at OPERA before light traveling along the same path would. If it is true this is the most significant find in physics for a century at least. For all practical purposes though, getting a result like this is a really good reason to check your equipment for obvious problems.<br />
<a name='more'></a> Having a particle like a neutrino (which has a rest mass) not just match, but actually exceed the speed of light is a discovery rather akin to the earth actually being hollow. It goes against so much previous evidence that it's probably wrong.<br />
Pure incredulity isn't the only reason to be reserved. We know muon-neutrinos don't normally travel faster than light; If they did, we'd have seen a bunch of them arrive well before the light from the recent Supernova in M101. Instead, everything hit us at roughly the same time. In addition, two experiments very similar to the one at OPERA (but admittedly at lower energies) didn't observe muon-neutrinos breaking the cosmic speed limit by and statistically significant amount.<br />
To their credit, the OPERA researchers seem to have taken every possible precaution to ensure that this result is real. They first observed this discrepancy almost six months ago, and since then, they've spent time making absolutely sure that they had the distance between the two labs almost exactly on (according to their paper, down to 20cm!), and making sure their timing systems were correctly synced up. They've repeated the experiment about 15,000 times with the same result, and they've take care to make sure there's no human bias sneaking in by blinding everything. Their <a href="http://arxiv.org/abs/1109.4897">arXiv paper</a> is mostly a meticulous write up of their methodology and specific objections still haven't shown up.<br />
What's next? Verification. If other sites observe muon-neutrinos moving faster than light, than we have the biggest experimental physics discovery of the past century. If they don't, the OPERA scientists missed something, and those 60 nanoseconds have been conjured out of the math. It'll be a some time before we know for sure.Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-81659676125501463722011-09-21T13:21:00.000-04:002011-09-25T19:26:02.049-04:00What is about to happen.Starting next week (and possibly this week for practice) you can expect
to see two new articles per week (posted on Saturdays?)on current events in science along with some
reasons you should care.<br />
As part of my first semester at MIT,
I'm taking a Science Journalism class. Part of this class is the
creation (and weekly updating) of a blog on science, medicine,
technology, and related topics.<br />
<a name='more'></a>Ninjinuity wasn't meant to be this
sort of blog when I created it. It obviously isn't exactly this sort of
blog right now. Going forward, however, I can only imagine that I will
continue to spend time on STEM topics, and I can only imagine that I'll
need to be in the practice of expressing myself cogently on them.<br />
This
is the reason I enrolled in Science Journalism. Even without the
course, weekly blogging on what interests me in current science seems
like an excellent idea.<br />
There probably isn't going to be much else posted for a while. If
I get the time to clean and post some sketches, great. If I get the
chance to work on the 3D scanner code or some other project, that'll
show up here too.<br />
The honest fact is that time at MIT is valuble. The coursework is quite
doable, but even once your work is done there's no end to the cool stuff
to do in your free time here. Blogging for fun comes in low on the
list.<br />
That's all. If you'll excuse me, I'm going to tool out this 18.03 Pset, then head to career fair.<br />
~WillNinjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-89413597463087093802011-09-06T22:16:00.000-04:002011-09-21T13:27:27.189-04:00Living in SimmonsMy sketching is still awful, but at least I'm getting the hang of cleaning it up in gimp... More after the jump.<br />
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaHatlb64loXG7pSsNbftUclbn3k06X8w0ZE9D9o1XJNRXBN1Ost66HYOoWGFF0_BHWhkznC6XGWjiWBpD9O8qpaRolhY-Zg6zBGU___Z6EBjWU3D1dv2y46D3ZBGFXAeIGSk6dcqDyg/s1600/347%257CA.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="299" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaHatlb64loXG7pSsNbftUclbn3k06X8w0ZE9D9o1XJNRXBN1Ost66HYOoWGFF0_BHWhkznC6XGWjiWBpD9O8qpaRolhY-Zg6zBGU___Z6EBjWU3D1dv2y46D3ZBGFXAeIGSk6dcqDyg/s320/347%257CA.png" width="320" /></a><br />
<a name='more'></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinU9Gbw0Qij6mvueGCsqQQ-tZuldmjx-xnlQztSxFz1iNhrOQ_vGSgKXClLuRouMTFbG1_XIU622oEfQYrhIRrDa4zNr1-AUxSPysgg5MH8skT7Hbs0EPStfQF-iUP39cKHtB9MAMXAg/s1600/Library.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEinU9Gbw0Qij6mvueGCsqQQ-tZuldmjx-xnlQztSxFz1iNhrOQ_vGSgKXClLuRouMTFbG1_XIU622oEfQYrhIRrDa4zNr1-AUxSPysgg5MH8skT7Hbs0EPStfQF-iUP39cKHtB9MAMXAg/s320/Library.png" width="313" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgTiSIpBnvWvF9PWlfRzfswRyfToeisQRbm_k8s3Z9lZ4NWWslvN0E4O6R58nHzan_i6zxASQnFuvS8jQhUfqF5WF61s1XoV7S10hETekTrheSyRy9MvxgOP6o3wC3y2-k3-KxCXVb8rg/s1600/F6Lounge.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgTiSIpBnvWvF9PWlfRzfswRyfToeisQRbm_k8s3Z9lZ4NWWslvN0E4O6R58nHzan_i6zxASQnFuvS8jQhUfqF5WF61s1XoV7S10hETekTrheSyRy9MvxgOP6o3wC3y2-k3-KxCXVb8rg/s320/F6Lounge.png" width="241" /></a><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqw9kqCdZhfLjqWyKPSbMYcsnPynlKbNPEOyxN_Hpq3WCExF3jZ9-KEHze9oK8QwcK3JhgmTW8_1pcF6fuqXvoEmilCKnITwDLen20dFpPc63oVhGywqtUPhUH-qvpQfCilx1zUXJV0w/s1600/Deathcube.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqw9kqCdZhfLjqWyKPSbMYcsnPynlKbNPEOyxN_Hpq3WCExF3jZ9-KEHze9oK8QwcK3JhgmTW8_1pcF6fuqXvoEmilCKnITwDLen20dFpPc63oVhGywqtUPhUH-qvpQfCilx1zUXJV0w/s320/Deathcube.png" width="268" /></a>Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com2tag:blogger.com,1999:blog-8175863459692085.post-19072902151431562922011-09-06T11:55:00.000-04:002011-10-01T21:45:33.691-04:00The Hough Transform: New and Improved! Ok, well it's still not better than a kerneled transform, but I am getting pretty pictures without the use of any trig! To sum up what I'm doing, I'm trying to use python's lambda expressions to generate a function in Cartesian space from the given points. Then I want to run BFGS over that function to find local maxima. By multiplying <span class="latex"> r = x_0 cos( theta ) + y_0 sin( theta ) </span> through by <span class="latex"> r </span> and rewriting as <span class="latex"> x^2 + y^2 = x_0 x + y_0 y </span>, it's easy enough to see that the hough transform of a given point is actually a circle with one point at the origin and centered at <span class="latex"> \left( \frac{x_0}{2},\frac{y_0}{2}\right). </span><br />
This has the nice property that it's easy to calculate the distance between a given line ( point in hough space ) and the nearest point on the circle as a single square root.<br />
<a name='more'></a><br />
On the down side, because the hough transform usually takes advantage of the distortion of euclidean distance for small <span class = 'latex'> \theta </span>, the end result has an absolute maxima at ( 0, 0 ). This maxima is very predictable, so I'm going to try just dividing by a function which is an idealized model near the origin, but quickly approaches 1 instead of 0 in every direction.<br />
Still, without further ado, some pictures:
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGg_64wwFTLV07vNR9PHnZ9wWtSOzuqDD-fzdgNHVmqg9t08wt8gPvLX3J_kQ1ifuZKMh4tICBEifoWQc7SBrzLn7VvSHfGEBXQ6kArLxkHVkzDmA615IPXZzORJrzx_h8J_2VQwCQpg/s1600/hough_test.png" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="183" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGg_64wwFTLV07vNR9PHnZ9wWtSOzuqDD-fzdgNHVmqg9t08wt8gPvLX3J_kQ1ifuZKMh4tICBEifoWQc7SBrzLn7VvSHfGEBXQ6kArLxkHVkzDmA615IPXZzORJrzx_h8J_2VQwCQpg/s320/hough_test.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"> This image shows a single line: x + y = 10. In hough space this
corresponds to the maxima at (5, 5). notice the nasty spurious point (0,
0).</td></tr>
</tbody></table>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHvwN_FVe0hRgl936cMwVSEd3s_A4osHwv_uSe5GSBSAIT6JS3J-rxFp4IKr66RQr0kjfdEdEndCpVuOsMzDu-GA1TaYYtEu_IzMnlA-kI1_Oi2gTZWa7p8Cp_Im9uDZFls-yh3NYxjA/s1600/hough_test3.png" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="183" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHvwN_FVe0hRgl936cMwVSEd3s_A4osHwv_uSe5GSBSAIT6JS3J-rxFp4IKr66RQr0kjfdEdEndCpVuOsMzDu-GA1TaYYtEu_IzMnlA-kI1_Oi2gTZWa7p8Cp_Im9uDZFls-yh3NYxjA/s320/hough_test3.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">x + y = 10, x + y = -10, and x + y = 20.</td></tr>
</tbody></table>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRCmhcrhyphenhyphenQ1pDKu-DrUiEhn5amjlem9kR0W-WFhl1QIEenEPbrc0tqkfZmnwTvoZFTP7MlNZVqprChAfKeKVSmYNbgwwW1jxsWfQakbdPkRdyNqb0yg4dsIKb1BCwFeFAWpVH7HuYUjQ/s1600/hough_test2.png" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="183" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRCmhcrhyphenhyphenQ1pDKu-DrUiEhn5amjlem9kR0W-WFhl1QIEenEPbrc0tqkfZmnwTvoZFTP7MlNZVqprChAfKeKVSmYNbgwwW1jxsWfQakbdPkRdyNqb0yg4dsIKb1BCwFeFAWpVH7HuYUjQ/s320/hough_test2.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Just x + y = 10 and x + y = 20</td></tr>
</tbody></table>
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<table cellpadding="0" cellspacing="0" class="tr-caption-container" style="float: left; margin-right: 1em; text-align: left;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhNXl78v7YU7NY8reK3inI0AOyETEOQvkIHLxWeZ7TML8laPasqAFc4yuRx-8TshEoJJeDa_ZwGzVCEjvo1_YmYKFCqOS3-9YVPHZvnhq2J4P4L4o8caKTaRD-x4Cx6NJjmiYAPpe2UXg/s1600/hough_test4.png" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="183" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhNXl78v7YU7NY8reK3inI0AOyETEOQvkIHLxWeZ7TML8laPasqAFc4yuRx-8TshEoJJeDa_ZwGzVCEjvo1_YmYKFCqOS3-9YVPHZvnhq2J4P4L4o8caKTaRD-x4Cx6NJjmiYAPpe2UXg/s320/hough_test4.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">x + y = 10, y - x = 10 and y = -7. This is a fairly unfavorable set of points. I think the top left maxima would be rather hard for a computer to locate.</td></tr>
</tbody></table>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="clear: right; margin-bottom: 1em; margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5t9rnHalMgGuwFDKOv7QtLKkeyfL5wiVngF59NMvEfQMeuyxAviYk-37n0wwH_0-xxtu6cjoZlHU5oChooSOulYgmQQKfgcuyC9NVbuFo6PBcxertRzCYNCMIBSt9evL_QaIiZL-Mvw/s1600/hough_test5.png" imageanchor="1" style="clear: left; margin-bottom: 1em; margin-left: auto; margin-right: auto;"><img border="0" height="183" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5t9rnHalMgGuwFDKOv7QtLKkeyfL5wiVngF59NMvEfQMeuyxAviYk-37n0wwH_0-xxtu6cjoZlHU5oChooSOulYgmQQKfgcuyC9NVbuFo6PBcxertRzCYNCMIBSt9evL_QaIiZL-Mvw/s320/hough_test5.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The same three lines as above, but this time I picked sample points in the triangle. Much easier to locate all three maxima. </td></tr>
</tbody></table>
<br />
<br />
Update: Quotienting out the central maxima works! This is the same triangle data set as above.
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOFXTtyQuYohKPV85bJRt8cbdRXYnhlAkTTtcE2e9-svo19hDx1YeSQ79KvUnFJgY9cL1w2d-PR-MJca9wqHFDEqNpRXUUFBJLSxM8rP0SxaJuXtKmh3fmSCNZL9ayrRFsthpeIesKvA/s1600/houghq_test.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="183" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOFXTtyQuYohKPV85bJRt8cbdRXYnhlAkTTtcE2e9-svo19hDx1YeSQ79KvUnFJgY9cL1w2d-PR-MJca9wqHFDEqNpRXUUFBJLSxM8rP0SxaJuXtKmh3fmSCNZL9ayrRFsthpeIesKvA/s320/houghq_test.png" width="320" /></a></div>
Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-17616539826787608972011-09-04T15:22:00.000-04:002011-09-21T13:28:16.847-04:00An awful haiku.Deathcube, what great mass!<br />
Rubber over the solid heart<br />
of a neutron star.Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-74692662985089797152011-09-02T12:08:00.000-04:002011-09-21T13:28:03.939-04:00A quick sketch from last night's "Welcome to Simmons" talk<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpt78UZ5rXHgopht6a38eLdJOAb13O6zllMscMQxu1IyU0tGswL0WI4S4vZwAAkGGh_nOcIa_fiJ5Q9WbAkItExWLK7wE48c4xdXVI62tiX6Zaq1fl5cniTYcIZriv5h0D_monFxsHgA/s1600/simmons-orient.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="223" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgpt78UZ5rXHgopht6a38eLdJOAb13O6zllMscMQxu1IyU0tGswL0WI4S4vZwAAkGGh_nOcIa_fiJ5Q9WbAkItExWLK7wE48c4xdXVI62tiX6Zaq1fl5cniTYcIZriv5h0D_monFxsHgA/s320/simmons-orient.png" width="320" /></a></div>
Done in the corner of some scrap paper. I've played around with some post editing in Gimp. Best part was the "Fire Alarm Prevention/ Popcorn Cooking 101" bit. Wish I could have sketched that instead, but I was out of paper space.Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-64104618561454239962011-09-01T20:59:00.000-04:002011-09-03T08:29:22.434-04:00A Native Google Talk Client for Linux(Sort of)I've been using Google Talk more frequently as of late, but upon investigation, I was disappointed to learn that Google hasn't released a Linux client for Google Talk. I did, however, notice a reference to a "native" (whatever that's supposed to mean) ChromeOS client. Since I knew that ChromeOS is running Linux under the hood, I decided to check it out. Amazingly, despite wads of yellow tape warning me that it would wreak havoc on my computer and slay my firstborn, it seems to work seamlessly as a Linux client for Talk in Ubuntu 11.04! Video chatting between two semi-native clients doesn't always work, and using both the client and, say, gmail chat at the same time has it's rough edges, but it's fine.Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-71182348594369136502011-08-30T21:16:00.000-04:002011-09-21T13:26:57.228-04:00Thoughts on Child Protection Legislation in Ireland[<a href="http://www.bbc.co.uk/news/uk-northern-ireland-14707515">BBC</a>] via [<a href="http://feeds.boingboing.net/%7Er/boingboing/iBag/%7E3/TLKzitDenvI/irish-catholics-object-to-child-abuse-disclosure-law.html">Boing Boing</a>]<br />
I'm not going to summarize the article above. That's been done enough. Just read it, poke around the issue for a while, then come back and read what I have to say.<br />
<a name='more'></a><br />
This is a story where I'd usually feel justified shaking my head, having a cynical little laugh for myself and quietly walking away without further thought. This is (as the Primate says) an issue about the role of religion in a free society, and more importantly, when religion gets to exempt itself where a secular organization cannot.<br />
I'll be upfront: I think that, in general, religious organizations should get no better treatment than a comparable secular non-profit, and often times they should be treated much like for-profit corporations, especially when it comes to potentially illegal activity they may engage in.<br />
I think that the ONLY situation in which it would be OK to exempt confessions (or any other similar religious ritual with as potentially severe secular repercussions) from the scrutiny of normal secular law (specifically laws concerned with issues like violent crime or child abuse) is if they are shown by a properly conducted, double blind trial to reduce repeat offenses when compared to secular methods and punishments.<br />
Given that this study would be difficult (if not just outright impossible) to conduct correctly, and the Church is about as likely to agree to engage in it as it is to reverse its stance on condoms, I think we ought to legislate on the null hypothesis until the Church sees fit to disprove it and the obvious null hypothesis is that confession is no
more effective than taking to a secular counselor.<br />
In short, I think the C. Church is in the wrong here. I don't care that this comes in the wake of a child abuse scandal in Ireland, and I hope I would say the same things if the C. Church had as impeccable a record in the child abuse department as it does in other areas.<br />
Religious exemption IS an very important part of a free society. The Primate is dead on there. Unfortunately protecting citizens from child abuse is more important role of government in my mind.<br />
On a related issue, I'm proud to say that my home state, Oregon, recently passed a bill explicitly removing exemption in cases where simple medical treatment could save children. I wish that parents letting their children die of treatable problems like Diabetes and Appendicitis for religious reasons was a non-issue. I wish I could write this both the Oregon bill and Ireland's policy off as political jousting directed at restricting religious freedom. I can't, because <a href="http://whatstheharm.net/children.html">children die of religious ignorance all the time</a>[whatstheharm.net - Very incomplete list, some entries are not due to medical ignorance.]. I can't dismiss the importance of this policy in Ireland because the Church's inaction in these cases has the potential to cause enormous harm to children (Again, I would be more than happy to revise my opinion here, of course, if the Church can show that Confession does a better job than Secular methods in a controlled trial.). That is a crime in the most basic sense of the word.<br />
With all that in mind, there are some amazing things happening here at MIT. Instead of ranting in my dorm room, I'm going to go out and get involved in some of them. Later.<br />
~NinjinuityNinjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0tag:blogger.com,1999:blog-8175863459692085.post-49918362783305750402011-08-20T08:42:00.000-04:002011-09-21T13:29:03.446-04:00Off to MITI thought for a long time about what I was going to say here to show that I wasn't scared. In the end, that would be a lie. I am scared, scared out of my mind.<br />
At least I'm excited.Ninjinuityhttp://www.blogger.com/profile/02542222531993130192noreply@blogger.com0