Axes of Evil

A quick and dirty set of 3D axes for Visual:

from visual import arrow, cylinder
 
def visual_axes( scale ):
    """\
    Display a set of 3D axes.
 
    @param scale: The scale of the axis set.
    @type scale: C{float}
    """
    for axis in [ tuple( [ i == j and scale * 5 or 0 for i in range( 3 ) ] ) \
                  for j in range( 3 ) ]:
        arrow( pos = ( 0, 0, 0 ), axis = axis, shaftwidth = scale / 10.0 )
 
    cylinder( pos = ( ( scale * 6.0 ), -( scale / 4.0 ), 0 ),
              axis = ( -( scale / 2.0 ), ( scale / 2.0 ), 0 ),
              radius = scale / 20.0 )
    cylinder( pos = ( scale * 5.5, -( scale / 4.0 ), 0 ),
              axis = ( ( scale / 2.0 ), ( scale / 2.0 ), 0 ),
              radius = scale / 20.0 )
 
    cylinder( pos = ( 0, ( scale * 5.5 ), 0 ),
              axis = ( 0, ( scale / 4.0 ), 0 ),
              radius = scale / 20.0 )
    cylinder( pos = ( 0, ( scale * 5.75 ), 0 ),
              axis = ( -( scale * 0.17 ), ( scale / 4.0 ), ( scale * 0.17 ) ),
              radius = scale / 20.0 )
    cylinder( pos = ( 0, ( scale * 5.75 ), 0 ),
              axis = ( ( scale * 0.17 ), ( scale / 4.0 ), -( scale * 0.17 ) ),
              radius = scale / 20.0 )
 
    cylinder( pos = ( 0, -( scale / 4.0 ), ( scale * 6.0 ) ),
              axis = ( 0.0, ( scale / 2.0 ), -( scale / 2.0 ) ),
              radius = scale / 20.0 )
    cylinder( pos = ( 0, -( scale / 4.0 ), ( scale * 6.0 ) ),
              axis = ( 0.0, 0.0, -( scale / 2.0 ) ),
              radius = scale / 20.0 )
    cylinder( pos = ( 0, ( scale / 4.0 ), ( scale * 6.0 ) ),
              axis = ( 0.0, 0.0, -( scale / 2.0 ) ),
              radius = scale / 20.0 )

Yep, this is how I’m validating my geometry module by eye.

Comments Off on Axes of Evil
Mar 22nd, 2010
Tags: ,

Topology, To What End?

There have been a number of approaches to build topological models of multi-camera networks. The idea is to represent, in some useful and relatively simple mathematical way, the relationship — usually meaning the overlap — between the fields of view of the cameras. To date, it seems as though all such methods fall into two basic types.

On one hand, we have the motion-based methods, which are typically targeted at tracking applications. Ellis et al. temporally correlate objects transiting between adjacent fields of view, after establishing each camera’s entry and exit zones. Similarly, Mandel et al. correlate simultaneous motion between views to establish overlap. Detmold et al. propose the exclusion algorithm, which is basically the opposite and potentially more robust: if there is motion in one view, and not in another, then those views cannot overlap (initially all views are assumed to overlap). Farrell and Davis present a slightly different model, dubbed the transition model, which focuses even more on tracking as it expresses the probability of transitions between views; this is also determined from observations of motion.

On the other hand, we have the feature-based methods, typically used as a precursor to or substitute for multi-camera calibration. Devarajan and Radke first proposed the vision graph without specifying an automated means of obtaining it; they later approached this topic in Cheng et al. using distributed matching of SIFT features. Kurillo et al. also use common features to build their vision graph for calibration. In my ICDSC 2008 paper, the vision graph is a theoretical upper limit for the grouping and calibration graphs, which are built from 3D feature matches via registration. Kulkarni et al. use a calibration target to explicitly match spatial points, and build an actual tessellation of 3D space to represent the range and degree of overlap of the cameras’ fields of view. Finally, Lobaton et al. use scene features (in their case, bisecting lines indicating wall delineations) to construct their algebraic topological model, which is proposed as a substitute for full calibration in certain (unspecified) secondary applications.

So is generic topological information about multi-camera networks only useful for tracking and calibration, the two problem areas that appear to have spawned every topological model in the literature? Are there any other applications that simply don’t have any convenient information of their own for building such models?

Comments Off on Topology, To What End?
Mar 19th, 2010
Tags:

Snap To Grid

I like Gabor Herman‘s definition of discrete Euclidean space. He defines, for any positive real number \delta and any positive integer N:

\delta \mathbb{Z}^N = \{ ( \delta x_1, \ldots, \delta x_N ) | x_n \in \mathbb{Z} \text{ for } 1 \leq n \leq N \}

This chops N-space up into a square (cubic, etc.) Bravais lattice, with primitive vectors of magnitude \delta. Each point in the discrete space is then associated with a primitive cell (or Voronoi neighbourhood, in Herman’s parlance) consisting of all points in the associated continuous space which are closer to that discrete point than any other discrete point.

This relationship to continuous space makes discretization of otherwise continuous sets — or regions, as say the GIS people — a snap (pun intended). In the simplest case, it is equivalent to basic sampling.

Voxels

In 3-space, these are essentially voxels, which are intuitive for visual thinkers like me, and allow for neat tricks from the computer graphics literature like voxel traversals.

Comments Off on Snap To Grid
Mar 17th, 2010
Tags: ,

Pi Day Madness

You have a right-handed Cartesian coordinate basis of a three-dimensional Euclidean space, with axes x, y, and z. You’re given some spatial-directional vectors of the form (x,y,z,\rho,\eta), where \rho and \eta are, respectively, the inclination angle (from the positive z-axis zenith) and the azimuth angle (measured right-handed from the positive x-axis) of an associated direction, which is unrelated to the direction of vector (x,y,z). How do you tell if the direction (\rho,\eta) of such a vector falls inside the exterior half-space defined by the plane normal to (x,y,z)?

If it helps, visualize it this way. Travel to a point in space (x,y,z). Then, find a point on the unit sphere surrounding (x,y,z) defined by (\rho,\eta) (like latitude and longitude). Now, cut all of space in half with a plane passing through (x,y,z) and perpendicular to the line between the origin and (x,y,z). Is the point on the unit sphere in the same half of space as the origin?

If x = y = 0, it’s dead simple: \rho \geq \pi/2. Doesn’t even matter what \eta is.

If y = 0 and x > 0, there’s no effect on the azimuth, so it’s still pretty straightforward: \rho \geq \pi/2 + \sin\eta\arctan(x/z). The \arctan(x/z) accounts for the tilt of the plane, and the \sin\eta accounts for the azimuth.

In the general case where x, y \not= 0, and thus the azimuth angle relative to the plane’s direction of tilt differs from the absolute azimuth angle, it gets a bit trickier. First, we need the magnitude of (x,y) for the \arctan bit:

r = \sqrt{x^2 + y^2}

Now, for z > 0, what we want is \rho \geq \pi/2 + \cos(\eta - \theta)\arctan(r/z), where \theta is the right-handed angle of (x,y) from the positive x-axis. Conceptually, subtracting \theta is like transforming the azimuth angle into a new coordinate system where the plane tilt is back in the xz plane (as if y = 0 and x = r). We could leave it like this, and have the reader calculate \theta as:

A Giant Ugly Mess

But, with a well-known trigonometric identity we can make it a bit prettier:

\rho \geq \frac{\pi}{2} + \left(\frac{y}{r}\sin\eta + \frac{x}{r}\cos\eta\right) \arctan\left(\frac{r}{z}\right)

More than a few scrap half-pages were harmed during the making of this inequality.

Comments Off on Pi Day Madness
Mar 14th, 2010
Tags: ,

LaTeX Preview with Vim and Evince

During a conversation (and a game of Scrabble) at the Google Summer of Code mentor summit, it came up that a few of us were LaTeX users, and we talked briefly about how it would be nice if there were some way to get a real-time preview the final document while editing in Vim. Here’s my solution.

I use make to build PDFs of my LaTeX files. A typical makefile looks like this:

LATEX= latex
DVIPS= dvips -j0 -Ppdf -u ps2pk.map -G0 -t letter -D 1200 -Z -mode ljfzzz
PS2PDF= ps2pdf -dEmbedAllFonts=true -dSubsetFonts=true
 
NAME= foo
FIGURES= images/*.eps
 
all: $(NAME).pdf
 
$(NAME).pdf: $(NAME).ps
    $(PS2PDF) $(NAME).ps $(NAME).pdf
 
$(NAME).ps: $(NAME).dvi
    $(DVIPS) -o $(NAME).ps $(NAME).dvi
 
$(NAME).dvi: $(NAME).tex $(FIGURES)
    $(LATEX) $(NAME).tex; $(LATEX) $(NAME).tex
 
clean:
    rm -f *.dvi *.ps *.pdf *.aux *.log *.lof *.lot *.toc

Knowing that Evince updates its view automagically when a file changes, I just added a post-write hook to my ~/.vimrc to run make:

autocmd BufWritePost,FileWritePost *.tex !make

Now, whenever I write the file out, my Evince window updates with the latest output.

I haven’t yet checked out Latexmk, which can supposedly effect similar results, and save me the trouble of maintaining a makefile to boot.

Comments Off on LaTeX Preview with Vim and Evince
Nov 15th, 2009
Tags: , ,

Loggerhead Init Script for Gentoo

I just set up a Bazaar repository server at work. Gentoo has no official ebuild for Loggerhead, so I installed it from Mark Lee‘s Bazaar overlay. Unfortunately, this does not ship with an init script for serve-branches, so I wrote one.

The script is /etc/init.d/loggerhead (mode 755):

#!/sbin/runscript
# Copyright 1999-2009 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
# $Header: $
 
PIDFILE=/var/run/loggerhead.pid
LOGDIR=/var/log/loggerhead
 
depend() {
    need net
}
 
start() {
    ebegin "Starting loggerhead"
    start-stop-daemon --start --quiet --background \
        --make-pidfile --pidfile ${PIDFILE} \
        --exec /usr/bin/serve-branches -- --log-folder=${LOGDIR} \
        ${LOGGERHEAD_OPTS}
    eend $?
}                               
 
stop() {                        
    ebegin "Stopping loggerhead"
    start-stop-daemon --stop --quiet \
        --pidfile ${PIDFILE}
    eend $?                 
}

This uses a single entry from /etc/conf.d/loggerhead:

LOGGERHEAD_OPTS="/var/bzr"

It seems to work. When I get the chance I may patch the ebuild to include it and suggest it to the maintainer.

Nov 12th, 2009

On Path and Edge Strengths in Fuzzy Graphs

How does one define the strength of a path in a fuzzy graph? Mathew and Sunitha state that “the degree of membership of a weakest [edge] is defined as [a path’s] strength” without any apparent justification. Saha and Udupa mention that several measures, including sum, product, and minimum, all seem plausible, but also ultimately choose the minimum for their purposes (based on a set of axioms related to their problem domain).

However, many methods of combinatorial optimization which operate on weighted graphs assume that the weight of a path is simply the sum of the weights of the edges which comprise it. In order for me to use such methods unmodified, I must define edge weight in terms of edge strength, and define path weight using the sum. I cannot, therefore, define path strength directly, and certain definitions (including the apparently popular minimum-edge one) are impossible to achieve this way.

Naturally, since the weight represents a cost of some sort and smaller weights are more desirable, edge weight should be inversely proportional to edge strength \mu. In FuzzPy, I simply take the inverse of \mu, which I now realize is naïve. In fact, a more correct basic definition would be 1/\mu - 1, so that an edge with \mu = 1 would result in a weight of 0.

A model of pairwise camera field of view overlap in a multi-camera network (fuzzy vision graph) is built of generally intransitive binary relations: if camera A overlaps with camera B, and camera B overlaps with camera C, camera A does not necessarily overlap with camera C, and almost certainly not to the degree implied by a transitive fuzzy relation. This intransitivity is the final nail in the coffin for non-sum-based path strength definitions in my problem domain.

Returning to the definition of edge weight, now in the context of multi-camera networks, there is something missing. Forgive me a contrived example of a problem such as calibration optimization. Intuitively, a path of eight edges each with \mu = 1 is likely to be less optimal than a path of a single edge with \mu = 0.9, because the definition of \mu does not fully encapsulate the pairwise calibration error (not least because the \mu values are normalized). Should edge strength be defined as 1/\mu - 1 + \alpha, where \alpha is some fixed accuracy (or other) cost for a single hop? My aforementioned naïve version (effectively, with \alpha = 1) has been working reasonably well in experiments. However, this extra parameter is not intrinsic to the fuzzy vision graph model, and thus must be defined by the optimization application.

The rationale behind the fuzzy vision graph is that it is a “quick and dirty” model of a camera network’s visual topology, and I think defining additional application-specific things like this α parameter at the optimization stage is appropriate.

Comments Off on On Path and Edge Strengths in Fuzzy Graphs
Oct 17th, 2009
Tags: ,

Thoughts in Kaoss

Yesterday, I spent the afternoon implementing the KMod hack on my Kaossilator thanks to a most excellent set of instructions. I used a DE-9 male connector, so I actually have 2 pins free for potential future additions (I wonder if I can cram something in there to output a MIDI-compatible tempo clock signal based on whatever is driving the little dot on the display).

I have plans for two things to plug into it now.

The first will be a simple little stub that just sits in the connector, with a 47K resistor and a switch in series between the SUO and SUI pins. I’ll make this as small as possible, and leave it attached most of the time for a portable sustain switch.

The second is my ambitious external control box. I’ll start with a basic set of buttons and toggle switches that control all the on-board functionality, including single buttons/switches for combos like key, loop length, and erase.

Next, I’m going to look into the feasibility of adding a port and circuit to allow some kind of synchronization from an external MIDI clock signal (probably not a huge deal, but I don’t yet know anything about MIDI really). This will be useful for syncing up with my x0xb0x, whenever I finish building it.

Finally, and most interestingly, I want to control functionality via my USB Boarduino. I’m going to develop a GUI application in Python (working title Kaosslab) that lets me do some really cool stuff. One tantalizing exampe is tempo-synchronized recording of loops (by having Kaosslab activate the loop button and record for the appropriate amount of time based on user-supplied tempo).

I also recently put up Kaossilator Fu on my web site. I’m working on populating it with every Kaossilator tip, trick, and hack I can find, as well as some videos of phat Kaossilator jams (like this one and this one and this one).

Comments Off on Thoughts in Kaoss
Jul 18th, 2009

Rollerblade Odometer

I want a pair of rollerblades that, using simple technology (no GPS), can fairly accurately report to me how far I’ve traveled. I want an odometer readout that I can reset before each trip. How can this be accomplished?

Add rotary encoders to the front and back wheels on the skate. We want the frictionless optical tachometer type; the direction of motion is irrelevant (picture someone skating backwards, for example). We can obtain a fairly accurate measure of the distance traveled by the skate by always recording the angular displacement of the faster-turning wheel. This can be accomplished by having each encoder increment its own small counter (say, a 4-bit one). When one of the counters overflows, it sends a signal to a large main counter and clears both small counters. The large counter is enabled by a pressure switch (maybe a piezoelectric sensor with a threshold for binary output) able to determine that the skate is in fact contacting the ground. At this point, assuming we’ve been intelligent about the encoder pitch relative to the wheel size, and done the appropriate trickery in the counting logic, we have a skate that can accurately measure its own ground distance traveled in some useful unit.

The major issue now is that both skates are sometimes, but not always, contacting the ground, and there is no way to know a posteriori, when observing the results, how much overlap to subtract. I don’t want to introduce any concept of time into this design, so what we need is some way for one of the skates to know whether the other is contacting the ground. We can accomplish this by having the pressure switch on the left skate enable an RF transmitter, with a simple structured signal that a receiver on the right skate can robustly identify. The receiver can then disable the counter on the right skate while the left skate is transmitting. Now, totalling the large counters in both skates should yield a fairly accurate total ground distance traveled.

However, as a human being, I can’t tell what is in those counters, and even if I could, I wouldn’t want to have to add them up in my head. We can add a button to the left skate that triggers a different RF transmission to the right which encodes its counter value and then resets it. The receipt of this signal on the right skate prompts it to add the value to its counter register and show the value on an LED display for a few seconds. This can be done repeatedly, since the left skate is just dumping its current counter value into the right skate each time, where the total is retained. The corresponding button on the right skate would simply reset its counter.

Some issues for further consideration:

  • Since the transmissions are one-way, the signal needs to be robust. We also assume that the rollerblades are both powered and in proximity to one another.
  • Power management. Should the skates power off after a period, and power on via the pressure switch? We likely want the main counter registers to be non-volatile.
  • Pressing a button on the left skate to activate a display on the right skate seems somewhat awkward from a user perspective.

I really ought to be doing more important things…

Jun 21st, 2009

Penguicon The Seventh

Like Xavier, I came back from Penguicon 7.0 this weekend to a mountain of work. Now I’m going to walk and talk like him (minus the epic growl) — guess that means I look like someone else here — and give my review.

The highlight was certainly the party. Friday night was phenomenal, Saturday night even more so. Where else can you be waylaid by a pirate ship at the top of the hotel lobby stairs, and told to drink rum and walk the plank to join the crew? Best Penguicon yet, on this basis. You have to be there to know.

The panels were good this year too, as usual. We could have attended a few more if it hadn’t been for a certain WTF line. Here are my thoughts on the ones I did catch:

Sustainable Computing (Jon “maddog” Hall)

A great forward-looking keynote by maddog. He deftly connected the idea of scalable distributed mesh networking for cities with providing free Internet access to kids (a la OLPC, but with fewer technical challenges), with benefits to everyone else too, and with environmental sustainability. And, naturally, he gave some highly compelling arguments as to why the sensible thing to do is use free software to implement it. A

Wil Wheaton Reading (Wil Wheaton)

Ensign Crusher, report to Penguicon. Ensign Crusher? Ensign Crusher, respond! F

Open Hardware Overview (W. Craig Trader)

A brief introduction to “open source” hardware. A big chunk of the talk was devoted to a few examples, which was surely a yawn-fest for anyone who reads hardware hacking feeds. The more interesting parts of the talk were the breakdown of the board prototyping process and the explanation of how projects apply licenses like Creative Commons to hardware design. A bit pedestrian, but not bad. B

Beginning Pygame Programming (Craig Maloney)

To be fair, I was very much looking forward to this one, so it had a lot to live up to. The talk consisted entirely of showing various stages of development of a Pong game demo. Much time was spent figuring out which revisions would actually run (blind commits are evil). A reasonable amount of Pygame functionality was used, but there could have been more explanation. Good concept, but tighter implementation necessary. C

Open Hardware with Arduino (W. Craig Trader)

This talk really made me wonder why Trader spent so much time talking about the Arduino platform in his previous talk. My main complaint is that he didn’t really contrast the advantages of the Arduino against other microcontrollers and evaluation boards, which probably left most people with a somewhat distorted perception. More original content, such as some clever uses and maybe a non-trivial demo, would have been nice as well. There was lots of good information about existing projects and add-on devices. I’ll give it a pass because it got the others interested. C

Rule-Based Programming in Interactive Fiction (Andrew Plotkin)

As an engineering grad student, I’m quite used to dry technical seminars, but I want Penguicon to entertain me more. That aside, awesome talk! I hadn’t really thought about how awkward it must be to program IF in an object-oriented programming language until this talk. Very interesting concept about how to attack the problem with a rule-based syntax model. Some of it brought to mind aspect-oriented programming. Bonus: Andrew really likes to talk about heads exploding. B

Looking forward to Penguicon 8.0! I’m hoping to get my Thousand Parsec talk in this time.

May 7th, 2009
Tags: