Friday, January 23, 2009

AutoShoop


An alternative to developing new technology is to apply existing technology in a new way. I was thinking about face recognition software a few days ago, and thought of a fun application (this isn't a serious project at all, by the way). So I quickly wrote AutoShoop, that uses a face-detection algorithm to draw "shoop da woop" shapes on people's faces. In other words, it automatically turns this:
into this: This works automatically - no Photoshop needed! I could have spent some time making the results better, but that's not really the point. It's more of a proof of concept.

autoshoop.zip (Windows GUI binary and sample images)
autoshoopsrc.zip (C# source)

I didn't write any of the face-detection part; I simply used fdlib. Your results may vary; I found that for some reason fdlib sometimes has a hard time finding faces in certain photos. When it works, though, it works pretty well.

Wednesday, January 14, 2009

Strangeparse

Let's say I want to be able to parse an arbitrary expression like
f(f( a+f(a * b * f(c))))

where a, b,c are variables, and f is some function. I want to make a parse tree, and possibly to transform the tree. Last night I thought of a very unorthodox way to do this.

I've heard of yacc/lex, pyparsing, and Python's ast. However, for what I have in mind this is all I need:
- Python supports overloading operators.
- Python has an "eval" for dynamically running code.

My idea is to create Python objects for f, a, b,c, and then *eval* the expression as if it were Python code. The objects I create will have their operators overloaded so that a+b, for example, returns an expression like ['+', a, b]. Here's an example that supports addition, multiplication, and functions taking any number of arguments. (Adding the rest of the operators is simple).
class FunctionSymbol:
  def __init__(self, name):
    self.name = name
  def __call__(self, *args):
    return SubExp(self, list(args))
  def __str__(self):
    return 'FN_'+self.name

class VariableSymbol:
  def __init__(self, name):
    self.name = name
  def __add__(self, other):
    return SubExp('OP_ADD', [self, other])
  def __mul__(self, other): 
    return SubExp('OP_MULT', [self, other])
  def __str__(self):
    return 'VAR_'+self.name

class SubExp(VariableSymbol):
  def __init__(self, op, args):
    self.op = op; self.args= args
  def __str__(self):
    return str(self.op) + '(' + ','.join(map(str, self.args)) + ')'

def strangeparser(s):
  #parse something by evaluating it as if it were Python code
    
  symbols = {}
  #create objects for the symbols in the string 
  snospace = s.replace(' ','').replace('\t','') + ' '
  import re
  for match in re.finditer('[a-zA-Z_]+', snospace):
    strfound = match.group()
    if strfound not in symbols:
      #assume that if the next character is "(", then it is a function
      if snospace[match.end()]=='(':
        symbols[strfound] = FunctionSymbol(strfound)
      else:
        symbols[strfound] = VariableSymbol(strfound)
  # evaluate it
  try: 
    return eval( s , globals(), symbols )
  except Exception, e: 
    print 'Could not parse. %s' % str(e)
    return None
  
def main():
  tree = strangeparser('a+b+c')
  print tree
  # OP_ADD(OP_ADD(VAR_a,VAR_b),VAR_c)
  tree = strangeparser('f(f( a+f(a * b * f(c))))')
  print tree
  # FN_f(FN_f(OP_ADD(VAR_a,FN_f(OP_MULT(OP_MULT(VAR_a,VAR_b),FN_f(VAR_c))))))

Also, I've written code that turns this tree into a sequence of simple operations. Coincidentally, I think this could be used to write a compiler. I haven't read any books about that, though.
input:
 f(f( a+f(a * b * f(c))))

output:
 i1=OP_MULT(a,b);
 i2=FN_f(c);
 i3=OP_MULT(i1,i2);
 i4=FN_f(i3);
 i5=OP_ADD(a,i4);
 i6=FN_f(i5);
 i7=FN_f(i6);
 return i7;
 

I'm working on a way to conserve the temporary variables used here, because there is probably a way to reuse them after they aren't needed. What I do is go down to the bottom of the tree, find something that can be evaluated, and replace that deepest node with a temporary variable. I then repeat that process until the whole tree has been "flattened".

Thursday, January 1, 2009

Homepage



On the internet, I now have a place that I can call my home. I've uploaded an initial version of a personal website.

It can be seen at http://downpoured.com (previously b 3 n f dot com).

(The section called "Recent Experiments" consists of links to this blog, but the other sections like Projects are new. There's a lot of content to explore.)

I've been working on this occasionally over the course of a few years, which is why the site doesn't seem very unified yet.

I intend to keep this blog active, though, so stay tuned.