Evil Instance Method Alternatives in Python

An evil way to exploit and abuse Python for fun and profit. I have no idea if this belongs in any real code, but if nothing else, call it an introduction to such neat Python features as metaclasses and decorators.

The idea is to create a class which allows specification of an instance-specific bound method (that is, a method that works like a normal method, with implicit self) in the constructor, from an internal set of alternatives, which are added externally using a decorator. The availability of the method should be enforced, but its implementation (and possibly signature) can vary. It should also be easily subclassed, and the set of options should follow the intuitive inheritance rules: subclasses inherit the base class’ alternatives, and can define their own new ones.

First, we will need to import MethodType, to allow dynamic creation of bound methods in instances.

1 from types import MethodType

Then, we define a metaclass that adds a class attribute called _options, which is an empty dict, to the class. The purpose of this dict (and of adding it through a metaclass, rather than directly in the class) will be seen shortly.

3 4 5 6 class EvilType(type): def __new__(cls, name, bases, attr): attr['_options'] = dict() return super(EvilType, cls).__new__(cls, name, bases, attr)

Now, we define the actual Evil base class. This is the root of the evil.

9 10 11 12 13 14 15 class Evil(object, metaclass=EvilType): def __init__(self, option): try: self.option = MethodType(self._options[option], self) except KeyError: raise KeyError('invalid option method %s' % option) self.integer = 0

First, notice the metaclass keyword in the class definition arguments: this tells Python to build the class through EvilType, which gives the class the _options dict. (In Python 2, this would be done instead using the __metaclass__ attribute.)

The __init__ constructor takes a positional argument, a string specifying the method alternative to use in the instance. This is the key to _options, paired with a callable taking one argument (trust me for a moment, it is). A KeyError will prevent the object being created, so every instance of Evil will have an option() method.

The integer instance member is just for demonstration purposes, and is not part of the evil.

So how does _options get populated with callables that can become bound methods? This is where the optionmethod decorator comes in.

17 18 19 20 21 22 23 24 25 26 27 28 @classmethod def _add_to_options(cls, name, func): cls._options[name] = func for subcls in cls.__subclasses__(): subcls._add_to_options(name, func)   @classmethod def optionmethod(cls, func): def wrapped(self, *args, **kwargs): return func(self, *args, **kwargs) cls._add_to_options(func.__name__, wrapped) return wrapped

optionmethod() is a class method, so it has access to the current class’ _options dict, when called as @Evil.optionmethod, for example. The wrapper itself is thin, but before the decorator method exits, it calls _add_to_options(), which adds the wrapped callable to _options of the current class and (importantly) all of its subclasses, recursively. Note that the signature of option() could be enforced by replacing *args and **kwargs in the definition of wrapped() with an explicit signature.

We also provide a convenient public way to get a list of available alternatives for option(). This could, for example, be passed as the choices parameter to an argparse argument definition.

30 31 32 @classmethod def options(cls): return cls._options.keys()

Now, we can define some subclasses, without doing anything special. The additional members here, again, are just for demonstration purposes and not part of the evil.

35 36 37 38 class EvilChild(Evil): def __init__(self, option): self.boolean = False super(EvilChild, self).__init__(option)
41 42 43 44 class EvilGrandChild(EvilChild): def __init__(self, option): self.string = 'foo' super(EvilChild, self).__init__(option)

And finally, we define a few method alternatives.

47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 @Evil.optionmethod def option_one(self): self.integer = 1   @Evil.optionmethod def option_any(self, integer): self.integer = integer   @EvilChild.optionmethod def option_two(self): self.integer = 2 self.boolean = True   @EvilGrandChild.optionmethod def option_three(self): self.integer = 3 self.boolean = False self.string = 'bar'

Now, off to a live Python interpreter!

>>> from evil import *

We can see that Evil indeed has the first two options.

>>> Evil.options() dict_keys(['option_one', 'option_any'])

Let’s try them out.

>>> asmodeus = Evil('option_one') >>> asmodeus.integer 0 >>> asmodeus.option() >>> asmodeus.integer 1 >>> bile = Evil('option_any') >>> bile.option(13) >>> bile.integer 13

>>> EvilChild.options() dict_keys(['option_two', 'option_one', 'option_any']) >>> cimeries = EvilChild('option_any') >>> cimeries.option(5) >>> cimeries.integer, cimeries.boolean (5, False) >>> damian = EvilChild('option_two') >>> damian.boolean False >>> damian.option() >>> damian.integer, damian.boolean (2, True)

And our sub-subclass?

>>> EvilGrandChild.options() dict_keys(['option_two', 'option_one', 'option_three', 'option_any']) >>> eblis = EvilGrandChild('option_three') >>> eblis.string 'foo' >>> eblis.option() >>> eblis.integer, eblis.boolean, eblis.string (3, False, 'bar')

Now, let’s be really evil and monkey-patch in a new option alternative.

>>> @EvilGrandChild.optionmethod ... def option_baz(self, integer, string='baz'): ... self.integer = integer ... self.string = string ... >>> EvilGrandChild.options() dict_keys(['option_two', 'option_baz', 'option_one', 'option_three', 'option_any']) >>> furfur = EvilGrandChild('option_baz') >>> furfur.option(9) >>> furfur.integer, furfur.string (9, 'baz')

Totally evil!

Feb 20th, 2013
Tags: ,

TI-92 Hacking, Day One

Day one hacking the TI-92 II graphing calculator.

Stuffed the beast with Duracell rechargeable AAs, and obtained a USB TI Connectivity Kit to talk to it. I have installed TiLP, TiEmu, and TIGCC on my Linux machine, and the official TI Connect software on my Windows XP virtual machine.

My goals for today are simple:

1. Connect to the device successfully with both TI Connect and TiLP.
2. Dump an original memory backup as a reference point.
3. Get an assembly shell loaded onto the calculator.
4. Dump a ROM image to drive TiEmu.

Connecting is simple enough, and TiLP dumps a serviceable backup file with a minimum of hassle.

The assembly shell gives me a bit more trouble. For the TI-92 II, the only apparent choice is Fargo II. On attempting to link the kernel into my backup file, the Linux binary for flinker acts up, and after a bit of poking I decide to just use the DOS binary, since I have the VM up anyway. I restore the modified backup with TiLP, and load the .92p files provided with Fargo to the device.

After installing the shell, dumping a ROM image with TiLP goes smoothly. The image is just over 2MB, and TiEmu is able to run it.

Jan 26th, 2013
Tags: ,

The Real and Imaginary of The Tea Party Live

With The Tea Party back together and touring again, and after seeing three live shows since last year’s reunion, I thought I’d set down some collected thoughts on the band’s catalogue and live performances. Naturally, this is all subjective, but I’ve provided links to the studio versions of the songs I mention, so you can form your own opinion if you like.

Splendor Solis

The original studio album containing many of the band’s tracks from the early days playing around Windsor (and the indie eponymous album), Splendor Solis still features strongly in live shows. Like on the album, The River is a great show opener. Save Me showcases Jeff Martin with the bow, and is a great live track besides. Sun Going Down is impossible to properly appreciate without hearing it live. The instrumental Winter Solstice often accompanies Sister Awake in an encore. In the early days I remember hearing A Certain Slant of Light a lot, but it’s been a long time.

Personally, I’d say there isn’t a single track on this album that wouldn’t sound great live. There is, however, a certain thread passing through Midsummer Day, Winter Solstice, and the last five tracks of the album that I imagine would sound really cool all strung together live. The riffs in Haze on the Hills prove it. In particular, I can’t ever remember hearing Dreams of Reason live, and it’d be my top pick.

The Edges of Twilight

The Edges of Twilight was the album that made The Tea Party’s live shows legendary. Fire in the Head is a staple, though I could live without it. On the other hand, The Bazaar is too much fun to give up. And then, of course, there’s Sister Awake, which ought to be considered one of the greatest rock songs of all time; the band has done some really cool stuff with this one live, from Led Zeppelin and Jimi Hendrix inserts to wholly new versions of the song, but it never quite lives up to the (heavily produced) album version.

Some of my other favourite tracks get played sometimes as well. I’ve heard Correspondences and Coming Home both since the reunion, and apparently the band has played Walk With Me as well (which I’d love to hear myself). Shadows on the Mountainside is beautiful; I think I heard this most recently during Jeff Martin’s tour with 777 in 2011. I find Inanna underrated, and the Alhambra version seems ideal for a live show. Finally, I remember once long ago hearing The Badger live, and really enjoying it.

Transmission

While Transmission is one of the stronger albums in The Tea Party’s catalogue, it doesn’t seem to be as suited to live performance as the others. This is probably a result of relatively heavy production and its dark tone (even by TTP standards). Nevertheless, Temptation and Psychopomp are staples in live shows, and having been to a few shows during this era, I’ve heard several others played.

My own top pick from this album would be Gyroscope, which, unfortunately, I’ve heard the band call their toughest track to play live. Another great one would be Emerald; even though the production is a big part of this track, I think a live version would have its own charm, and although I’ve never heard of the band as a whole playing it, we at least have an apparent precedent of Jeff Martin playing it solo. I think Stuart Chatwood could sink his synth teeth into either of these tracks.

Triptych

Of all The Tea Party’s albums, I’m probably happiest with the representation Triptych gets in concert. Without a doubt, The Halcyon Days is my favourite track from this album, and it’s a staple, sometimes with really cool inserts (like Dead Can Dance’s Rakim or Led Zeppelin’s Kashmir). Their big hit, Heaven Coming Down, is always present, but I’m not complaining, it’s an undeniably great song. I used to gripe about The Messenger, but lately either the guitar is getting more awesome, or else I’m appreciating it more.

This is another heavily produced album, so of the songs I really dig, I’m not sure how many (besides the aforementioned) would really translate well live. I think the one exception might be These Living Arms.

Tangents

As a compilation, there are only a few original tracks on Tangents. Of these, I can only ever remember hearing Walking Wounded live (besides Paint it Black being used as an insert with Sister Awake).

My only thought here is that Lifeline would be amazing live, done with the right instruments.

The Interzone Mantras

Despite The Interzone Mantras representing The Tea Party’s return to more of a “live” sound, it doesn’t seem to get much live play. I can only remember seeing one show between 2001 and 2004, so if the band ever played a lot of this material live, I guess I missed it. The major exception is Lullaby, which makes decent live material.

There are a couple tracks on this album I’d like to hear live, and since the production is so light, they should sound great. My top pick would be Cathartik: it showcases some incredible guitar and drums. I think The Master & Margarita has a bit of the flavour Jeff Martin was going for with 777, which made great live rock.

Seven Circles

The last studio album, Seven Circles, naturally got a lot of live play pre-breakup. Writing’s on the Wall was a hit and makes a pretty good opener, but honestly, there are so many other good tracks on this album, it’s not even worth bothering in my opinion. And if I never hear Oceans played live again, I won’t miss it.

Mainstream sound or not, I think this is a hugely underrated album. I’m just not sure how many of its tracks would make good live material. I can imagine Luxuria being great, and it carries a lot of the classic Tea Party sound. Between that and Coming Back Again, Jeff Burrows would really get to show off on percussion. Overload seems like it would be fun too. Finally, I can imagine a live version of Empty Glass being popular.

Sep 1st, 2012
Tags:

Modular Command Interface in Python

Adolphus implements a neat little interactive command interface in Python. It grew rather organically, so for all I know it’s a bizarre way of doing something available in some library. In any case, it’s pretty light and does what I need, so maybe you’ll find it useful too.

The commands module first defines an empty dictionary of commands. The keys are the command names, and the values are the associated callables.

38 commands = {}

It also defines a simple custom exception class, which currently does nothing interesting besides being identifiable.

40 41 class CommandError(Exception): "Command failed (usually non-fatal)."</code>

The interesting part is the @command decorator. This applies to any function taking 3 arguments, viz. a reference to the Experiment object, a list of strings comprising the command arguments, and a string specifying the output format of the command (pickle, csv, or text). The response check is a developer-level assert. Other exceptions arising from the call to the wrapped functions could be user-level errors, and the interface should be able to handle these as run-time CommandError exceptions, hence the try block. The docstring of the wrapped function is expected to provide usage details, so it is adopted by the wrapper function. Finally, the command is added under the name of the function to the commands dictionary.

44 45 46 47 48 49 50 51 52 53 54 55 def command(f): def wrapped(ex, args, response='pickle'): assert response in ['pickle', 'csv', 'text'] try: return f(ex, args, response) except CommandError as e: raise e except Exception, e: raise CommandError('%s: %s' % (type(e).__name__, e)) wrapped.__doc__ = f.__doc__ commands[f.__name__] = wrapped return wrapped

Since the @command decorator lives in the module, and the ex argument is passed in, the developer can define custom commands outside of the module itself, simply by importing the decorator and (optionally) CommandError. This was the factor that drove the design.

The following is a relatively simple example of a command definition. In this case, it catches a possible exception from its main action to offer a more meaningful error description to the user.

479 480 481 482 483 484 485 486 487 488 489 @command def setactivelaser(ex, args, response): """\ Set the active laser to the specified laser.   usage %s laser """ try: ex.model.active_laser = args[0] except AttributeError: raise CommandError('not a range coverage model')

The main example of calling a command is given by Experiment.execute(). In this case, any CommandError is re-raised with an appended usage message.

351 352 353 354 355 356 357 358 359 360 361 362 363 364 cmd, args = cmd.split()[0], cmd.split()[1:] if cmd not in commands.commands: raise commands.CommandError('invalid command') try: return commands.commands[cmd](self, args, response=response) except commands.CommandError as e: es = str(e) if commands.commands[cmd].__doc__: for line in commands.commands[cmd].__doc__.split('\n'): line = line.strip(' ') if line.startswith('usage'): es += '\n' + line % cmd break raise commands.CommandError(es)

It is also possible to define “meta-commands” that operate on the command system itself, as long as they have scope access (e.g. are defined within the commands module). The following example allows the definition of run-time aliases to commands which optionally force some or all of the command parameters to fixed values.

58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 @command def alias(ex, args, response): """\ Create an alias to another command, optionally forcing some or all arguments.   usage: %s alias command [argument]* """ def wrapped(wex, wargs, response): assert response in ['pickle', 'csv', 'text'] try: return globals()[args[1]](wex, args[2:] + wargs, response) except CommandError as e: raise e except Exception, e: raise CommandError('%s: %s' % (type(e).__name__, e)) wrapped.__doc__ = globals()[args[1]].__doc__ commands[args[0]] = wrapped

Simple, clean, and Pythonic.

Aug 16th, 2012

What The Hare Said To Hector

Hector: Alright, explain your game to me, Mr. Hare.

Hare: First, I will stand somewhere along the race track, but I won’t tell you where, and this wall hides me from view. Now, do you see this large contraption here?

Hector: Indeed. There is a $l$-meter long net suspended from a high cable that extends along the track between two poles. Attached to the pole at this end (behind the wall) is a box with a crank, a lever, an anemometer, and a graphing calculator. I surmise that the crank moves the net along the cable, and that the lever releases it.

Hare: Very astute!

Hector: And I suppose that my goal is to trap you under the net?

Hare: Without any information to guide you? No such nonsense. In fact, the game is much more subtle than that. You will indeed crank the net to a position of your choosing — let’s name the end closest to you $n$ — and then release it. I will then reveal my position — call it $h$ — to you, and you must wager with me on whether I am under the net.

Hector: Too easy! If $n \leq h \leq n + l$, then I wager that you are under the net; otherwise, that you aren’t. I can’t lose!

Hare: Ah, not so fast. You see, there are random winds along the direction of the race track in these parts, and so the net may be blown considerably off from a straight downward course.

Hector: Which, of course, I won’t be able to see, due to the wall.

Hare: Precisely.

Hector: So, we could say that the net covers not $[n, n + l]$, but $[u, u + l]$, where $u$ is a $n$-mean Gaussian process with standard deviation $\sigma$.

Hare: If you like.

Hector: Hence the anemometer, from which I can estimate $\sigma$. I see. Thus, my task is reduced to the following: given $n$, $l$, $\sigma$, and $h$, compute the probability that $u \leq h \leq u + l$. From there, I can decide whether the wager has a positive expected value for me.

Hare: Well played, Hector. But there is still one outstanding consideration.

Hector: And that is?

Hare: Actually computing the probability you speak of quickly enough to make your wager! I have somewhere to be promptly after this game, and as you know, we leporids hate to be late…

And with that, the Hare races off around the wall and down the track.

Jan 20th, 2012

Miss Register, I Presume?

In my AIM 2010 paper, I describe how to obtain a projective transformation $\mathbf{H}$ from the image plane to the laser plane in a line laser 3D range imaging system. With the laser oriented vertically (i.e. perpendicular to the transport direction of the object being scanned), this allows for mapping of image coordinates directly to 3D coordinates.

Specifically, the $(u, v)$ coordinates of a point in the image map through $\mathbf{H}$ to yield the $(x, z)$ coordinates in the laser plane. Then, if $y_\Delta$ is the transport direction offset between profiles, the 3D coordinates of such a point in profile $i$ are $(x, i y_\Delta, z)$.

There is an additional step when the angle between the laser and the vertical axis is nonzero, as in the common configuration shown below, where the camera (rather than the laser) is orthogonal to the transport surface.

In this case, knowing the angle $\beta$ is the key. Assuming the transport direction is positive away from the laser side and the object runs toward the laser, a point $(u, v)$ in the image maps to 3D coordinates $(x, i y_\Delta - z\sin\beta, z\cos\beta)$, where $x$ and $z$ are found as before.

I have a feeling that it is possible to derive $\beta$ from $\mathbf{H}$. More formally, given the $3 \times 3$ matrix representation $\mathbf{H}$ of a projective transformation between two planes $P_1$ and $P_2$, and supposing $L$ is the line of intersection of $P_1$ and $P_2$, what is the angle $\alpha$ between vectors $\vec{n}_1$ and $\vec{n}_2$ lying, respectively, in $P_1$ and $P_2$ and perpendicular to $L$?

Jun 4th, 2011

Rise of the Quaternions

Adolphus finally quit messing around and started using a quaternion representation for rotations internally! The quaternion class itself is simple, and conversion to and from rotation matrix and axis-angle representations is fairly straightforward. The magic happens in converting from Euler angles — all twelve valid conventions!

By solving the conversion to quaternion for all twelve possibilities, I managed to squeeze out a pattern that allows me to solve them with a near-minimum of redundant code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 @staticmethod def from_euler(convention, angles): def qterm(index): bin = lambda x: [(x >> 2) % 2, (x >> 1) % 2, x % 2] return copysign(1, index) * reduce(lambda a, b: a * b, [(bit and sin or cos)(angles[i] / 2.0) \ for i, bit in enumerate(bin(abs(index)))]) # TODO: can these be generated from the convention? eulerquat = {'xyx': [0, -5, 1, 4, 2, 7, 3, -6], 'xyz': [0, -7, 1, 6, 2, -5, 3, 4], 'xzx': [0, -5, 1, 4, -3, 6, 2, 7], 'xzy': [0, 7, 1, -6, -3, 4, 2, 5], 'yxy': [0, -5, 2, 7, 1, 4, -3, 6], 'yxz': [0, 7, 2, 5, 1, -6, -3, 4], 'yzx': [0, -7, 3, 4, 1, 6, 2, -5], 'yzy': [0, -5, 3, -6, 1, 4, 2, 7], 'zxy': [0, -7, 2, -5, 3, 4, 1, 6], 'zxz': [0, -5, 2, 7, 3, -6, 1, 4], 'zyx': [0, 7, -3, 4, 2, 5, 1, -6], 'zyz': [0, -5, -3, 6, 2, 7, 1, 4]} a, b, c, d = [sum([qterm(eulerquat[convention][i + j * 2]) \ for i in range(2)]) for j in range(4)] if a > 0: return Quaternion(a, -b, -c, -d) else: return Quaternion(-a, b, c, d)

Now, those hard-coded sequences of numbers? I am sure there is some relationship between the patterns and the conventions that would allow a more concise translation from one to the other. Note that, for a sequence [a, b, c, d, e, f, g, h], any or all of the pairs (a, b), (c, d), (e, f), and (g, h) can be swapped without changing anything (for example, the sequence for zyx could just as easily be [0, 7, 4, -3, 2, 5, -6, 1]). This has the unfortunate effect of making finding a pattern more difficult.

There are a number of tantalizing clues. The first number is always 0. The second is always -5 when two of the rotations are about the same axis, -7 when they are all different and in (rotated) xyz order, and 7 when they are all different and in zyx order. The 1 is always positive and appears in the second pair when the first axis is x, the pair when y, and the fourth when z. And so on.

I wonder if anyone else has figured out something similar? Adolphus wants a 9-line conversion function for its birthday.

Oct 18th, 2010

Rotating Lines

Problem:

Given a line of slope m in the Euclidean plane, what is the slope m’ of the line rotated (counterclockwise) by angle θ?

Solution:

Suppose we have an equation for the line of the form y = mx + b. We can ignore b as it is unrelated to the slope (in effect, we are working in an affine space).

So, y = mx for our purposes. Every point satisfying this equation is a multiple of

$\left[\begin{array}{c}1 \\ m\end{array}\right]$

and, similarly, every point satisfying the equation y = m’x of the rotated line is a multiple of

$\left[\begin{array}{c}1 \\ m'\end{array}\right]$

Since the latter point is the image of the former after rotation by θ, the points are related by a rotation matrix, like so:

$\left[\begin{array}{c}1 \\ m'\end{array}\right] = \left[\begin{array}{cc}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta\end{array}\right] \left[\begin{array}{c}1 \\ m\end{array}\right]$

Solving for m’ then yields

$m' = \frac{\sin\theta + m\cos\theta}{\cos\theta - m\sin\theta}$

which, of course, is our solution in terms of m and θ.

Jun 28th, 2010
Tags:

So Close, Yet So Far Away

I humbly entreat any analytical intellects of greater constitution than my own (of which, to be sure, there is no dearth) to enlighten me in matters mathematical.

First of all, if I have a 5-dimensional space which consists of a 3-dimensional Euclidean space plus direction (defined by inclination and azimuth) — that is, the set of vectors $(x, y, z, \rho, \eta)$ where $x, y, z \in \mathbb{R}$, $\rho \in [0, \pi]$, and $\eta \in [0, 2\pi)$ — what is that called? Of course, this generalizes to a (2p – 1)-dimensional space with a p-dimensional Euclidean spatial component. I have been calling fuzzy subsets of this space spatial-directional fuzzy sets, but spatial-directional space sounds patently ridiculous.

Second, is it possible to define a useful distance metric in such a space? Chaudhuri and Rosenfeld generalize the Hausdorff distance to arbitrary fuzzy subsets of a metric space, but this is of little use to me if my universal space is not metric. The natural way to define distance between two directions is to use the angle between the corresponding vectors, or similarly a norm on the surface of a torus. The obvious problem is that the numbers used for space and angle bear no relation to one another, so it seems nonsensical to combine them in a single metric (scaling and other such hackery need not apply). Yet, configuration spaces with similar discord among the units of their dimensions abound in engineering. Surely someone has tried to do something like this before?

Jun 15th, 2010
Tags: ,

In my M.A.Sc. work on stereo camera network calibration, I made use of a series of graphs to describe the relationships between nodes. Existing work had already produced the vision graph and what I will call the transition graph (after Farrell and Davis‘ transition model). In both graphs, each vertex represents a node (camera or camera pair, usually) in the multi-camera network.

The Vision Graph

In a typical sensor network, the sensing modality is simple and omnidirectional, and thus adjacency is a function of proximity. A consequence of this is that the sensing graph is usually a subset of, equal to, or a superset of the communication graph. Therefore, it is usually possible to cheat by initializing the sensing graph model using either physical topology (from, say, GPS) or communication topology.

Camera networks break from this in that their sensing modality is complex and directional, so sensing adjacency has relatively little to do with communication adjacency. Devarajan and Radke realized this early on, and proposed the vision graph. An edge in the vision graph represents information about shared field of view between the two nodes represented by its vertices; there is an edge wherever there is significant overlap of the observed scene. But what does significant mean? Assuming we’re referring to a classic, unweighted graph for the moment, in order for it to be useful, significant must mean that there is sufficient overlap that we can – or at least, that it is reasonable to expect that we could – achieve whatever task is intended for the shared data.

Since every published use of the vision graph I am aware of is a calibration application, let’s talk about that. Originally, Devarajan and Radke had to specify the vision graph manually a priori in order to use it for calibration; a follow-up with Cheng proposed a method to build it by propagating digests of SIFT features from the various images to other nodes. I myself only used it in concept, as a theoretical upper limit for the final calibration graph.

Now, for a digression…

The Transition Graph

Meanwhile, folks working on surveillance and tracking applications were also using a graph formalism – well, in most cases, a reflexive binary relation on the set of nodes that translates trivially into a graph formalism. An edge in the transition graph represents a different, although related, kind of adjacency between the two nodes represented by its vertices: the possibility of a target moving from the field of view of one node to that of the other. This, of course, includes overlapping fields of view, but importantly, it also extends to the non-overlapping case.

It quickly became clear to someone that it was worthwhile to represent not just the possibility, but the probability, of a transition. This may have been an obvious consequence of some of the methods used to actually determine this graph or relation – for example, Marinakis et al. used a Monte Carlo expectation-maximization method, and Farrell and Davis used sequential Bayesian estimation, both probability-oriented. Though intended to properly capture the information presented, it turns out that weighting the graph with these probabilities allows for some good optimization when it comes time to do predictions or camera hand-offs.

The Fuzzy Vision Graph

Seeing this, we thought, what if we similarly retain the uncertainty in the vision graph (rather than thresholding it out on an task-specific basis, as in all prior work) and put it to work optimizing calibration and other applications? Probability is, in general, ill-suited to the job, because we aren’t talking about transitions here. So, we considered another representation of uncertainty: fuzzy sets. A graph is an ordered pair $(V, E)$ of a set of vertices $V$ and a set of edged $E$; a fuzzy graph (in most definitions) is simply a generalization where $V$ and $E$ are fuzzy sets.

One nice thing immediately apparent is that, with the inherent, well, fuzziness of fuzzy graphs, there’s no longer any need to set task-specific thresholds in advance when constructing the model; instead of summarily judging whether overlap is significant, we simply capture the degree of significance, which if we really want can be thresholded later via task-specific alpha cuts. Beyond this, a number of opportunities for automatically optimizing various tasks in more advanced ways presented themselves as I poked at the idea. (This is the time when FuzzPy was born.)

The major problem, so far, is that there is no real understanding of what the ideal fuzzy vision graph actually represents. We can build them in various ways: using feature digests like Cheng, for example. But in order to decouple the practical optimization research from the practical modeling research, we need some definition of what a perfect vision graph for a camera network actually is.

Modeling Camera Network Coverage

To approach the problem of modeling the topology of camera coverage overlap, what is really needed is a proper model of camera network coverage. Much of the existing work on this has been developed specifically for optimal camera placement algorithms; it provides some inspiration, but as these models are rather simplistic (discrete, two-dimensional, triangular in shape, etc.) they don’t provide much in the way of an ideal model. Delving deeper, some decades-old work on task-oriented camera placement by Cowan and Kovesi provides an idea for a more realistic model of camera coverage, if you invert it, but is only for single cameras and uses task-specific thresholds.

Coverage, like overlap in the vision graph, is an imprecise concept when it is not tied to a specific task. Hence, fuzzy sets once again presented themselves as a possible framework for the representation: one can assign a membership degree in the set of covered points to every point in three-dimensional Euclidean space. Like Cowan and Kovesi, I identified visibility, focus, and resolution as the major factors in single-camera coverage (in the absence of a priori scene knowledge), developed “trapezoidal” fuzzy sets for each, then combined them via algebraic product fuzzy intersection to get a complete model that, given the intrinsic parameters of a camera and a couple of intuitive application (not necessarily single-task) parameters, would tell me how well any point in its local 3-space is covered. This is called the fuzzy coverage model.

It becomes evident that a fourth factor, direction, is needed when looking at the multi-camera case, where cameras are situated in a common coordinate system based on their extrinsic parameters, and we are interested in part in their field-of-view overlap. If two cameras face the same general volume of space, but from opposite sides, is the volume in common covered by both cameras? If you’re tempted to think yes, consider a task such as feature matching. Cameras can only see opaque surfaces with normals in the interior half-space defined by a plane tangent to the point in question and perpendicular to the principal axis. Furthermore, a number of studies have shown that, in practice, feature matching performance degrades over rotation of the viewpoint. Thus, if we extend our three-dimensional concept of space to include direction as well, making the fuzzy coverage model 5-dimensional, we consider points at the same location in 3-space but with different direction not the same point at all. Some geometry and a fuzzifying parameter gives us another component fuzzy set for the single-camera model, which we can incorporate by algebraic product intersection.

Another major consideration for the multi-camera case, which various work on camera network topology and placement optimization has attempted to tackle, is occlusion from the static scene. This may be known a priori (e.g. CAD layout of a building) or estimated by the camera network itself. It is possible to do this in continuous space, like ﻿Tarabanis et al., and so ideally you’d have a complete 3D model of the unoccluded field of view for each camera, and all other points have $\mu = 0$. However, the complexity seems prohibitive in practice for large camera networks. If we instead move to a discrete representation of the fuzzy coverage model, we can do what I did: make the scene finite, mark a subset of its voxels opaque, then use the voxel traversal of the line from a given point to the principal point of the camera to determine whether it is occluded (i.e. if the traversal includes any opaque voxels).

The easy part is the total network coverage. For simple multi-camera networks, where one camera covering a point (remember, we account for direction implicitly) is enough, simply combine all the appropriately transformed, discretized, and occlusion-ified single-camera coverage models together via standard fuzzy union. For 3D multi-camera networks, where we want at least two cameras covering a point, first generate a coverage model for each pair of cameras via standard fuzzy intersection on the pair, then combine all these via union.

Okay, now what?

This is about where I’m at. There’s plenty more that could be done with the fuzzy coverage model itself: solving the optimal camera placement problem in new and exciting ways is one really obvious possibility that I talk about in an upcoming paper.

As far as getting back to the graph stuff, I defined an overlap metric involving the scalar cardinality, which could be used to derive the fuzzy vision graph from the discrete fuzzy coverage model; this is significant in that it indicates a direct link from the $\mu$ values of the edges all the way back to the basic parameters of the camera network and the scene (and we know where all the simplifications are). Even better, though, might be something more analytic and general, like using something along the lines of the Hausdorff distance between two cameras’ coverage models, which might not only allow us to find the fuzzy vision graph, but also start unifying it with the non-overlapping concept of the transition graph.

Back to the future…