Michael Friis' Blog

About


Video of procuring authorities in the EU

I did a video showing the geographical spread over time of authorities buying stuff through the EU public procurement system. We managed to hijack all the contracts some time ago and the addresses of the authorities and the winning contractors have now all been geocoded. You can also explore the data on the TEDBot website.

The animation starts in january 2003 and ends at the end of 2007. You can actually see the EU expansion happening in May 2004 with dots spreading east. 10 14 day intervals are shown each second. The animation was generated with Processing.

Techniques for unique, correct and fast geo-queries

UPDATE: Better solution here.

Here’s the scenario: You have a lot (a million+) of geotagged addresses in a database and you want to show them as markers on Google Maps. Some further requirements are:

  • You only want to show some constant (10) amount at any given time, since too many markers clutters the map and kills the browser
  • You want the markers shown for a given frame to be selected randomly so that a user looking at some particular area with many geocoded addresses is not always shown the same 10 markers
  • You want the markers not to be on top of each other, so that even though many addresses in the database have the same coordinates (i.e. “Copenhagen, Denmark”), you only return one result per coordinate (this is to avoid placing two or more markers in the same spot)
  • You want it to run at interactive speed on a crummy box

Imagine you have a Documents table with columns including geoLng, geoLat representing geographical coordinates and intid, a unique integer identifier. @maxcount is the maximum number of rows desired while @maxLat, @minLat, @maxLng and @minLng define the corners of the map viewport. This query will do the job:

select *
from Documents dd
where dd.intid in
(
    select top (@maxcount) max(intid)
    from Documents d
    where d.geoLat < @maxLat
        and d.geoLat > @minLat
        and
        (
            ((@maxLng > @minLng) and (d.geoLng < @maxLng and d.geoLng > @minLng))
            or
            ((@maxLng < @minLng) and
            (
                (d.geoLng > @minLng and d.geoLng < 180) or
                (d.geoLng > -180 and d.geoLng < @maxLng))
            )
        )
    group by d.geoLng, d.geoLat
    order by newid()
)

“What’s this monkeying around with the longitudes?” I hear your cry? Well, if the map viewport straddles the International Dateline (which is somewhere in the Pacific), Google Maps will feed you viewport corners that “wrap around” and that has to be handled. If-elses in SQL is a mess, so it’s better to cook up some pure boolean voodoo like above. “Who the hell looks at Google Maps of the International Dateline?” you ask. Good point, but it’s actually not that uncommon. Looking at Japan at low zoom-levels will often provoke this behaviour, as will looking at French Polynesia. Note that this trick is not needed for latitudes because the maps don’t wrap vertically

The slowest bit will usually be the order by newid() part, which gives each row in the prospective result a new (random) guid, and then sorts all the rows based on this column. It can be replaced with tablesample calls which are much faster, but also a lot more erratic.

There’s a very slight problem with this query in that the max(intid) will always cause the same row to be returned for any given Lat/Lng coordinate. The use of max(intid) is completely arbitrary and min(intid) would work too. Had there been a rand(intid) aggregate, the problem would have been solved. I haven’t figured out an elegant solution to this problem yet. Note that max()doesn’t work on guids produced by newid().

To get this to perform, the tables in question are organised around a clustered (geoLat, geoLng, intid) index. You can see somewhat more elaborate versions of this query doing their thing at the TEDBot website.

Using WCF to power Facebook feedstory forms

UPDATE: I think Facebook has changed the API so that links in full stories have to be split into src and href parts.

Several parts of the Facebook developer API requires application developers to furnish JSON web services that feed data to various actions. These include feed forms (“I want to stick something on my wall”) and the publisher to name a few. This post will descripe how that JSON can be generated through Windows Communication Foundation web services. You can see this code in action in the simple Louisefy application. Note that alternatives certainly exists (I recommend Json.NET), but now that we have WCF, why not use it?

(As Rune points out in a comment below, you can use the object-hierachy in the code to generate compliant JSON even if you’re using Json.NET instead of WCF).

As far as feed forms go, the developes pre-register a range of templates for the kind of stories they want their users. A set of templates that get fed to Feed.registerTemplateBundle might look like the following:

List oneLiners = new List() {
	"{*actor*} is <a href=\"{*linkurl*}\">{*linktitle*}</a> {*target*}s Facebook",
};
List shortTmplts = new List() {
	new Dictionary() {
		{"template_title","{*actor*} is <a href=\"{*linkurl*}\">{*linktitle*}</a> {*target*}s Facebook"},
		{"template_body","."}
	},
};
Dictionary fullTmplts = new Dictionary() {
	{"template_title","{*actor*} is <a href=\"{*linkurl*}\">{*linktitle*}</a> {*target*}s Facebook"},
	{"template_body","{*swf*}"}
};

The FBML markup to get a feed form that lets users publish on their friends feeds would look like this:

<form fbtype="multiFeedStory" action="http://link.to/myfeedhandler.svc">
Start typing names of your friends:
<fb:multi-friend-input />
<input type="submit" label="Louisefy your friends feeds" />
</form>

The code for the actual feedhandler follows below, with the web.config stuff at the very bottom. I really like the terse, declarative syntax — there’s not a single hint that this all becomes JSON at some point. Note that if you need to pass arguments to your feedhandler, they’re very easy to map in the UriTemplate. I generally find WCF services to be fiendishly complex to get up and running because of the dearth of good tutorials and documentation — but once you get them going, it’s pure joy.

[ServiceContract]
[AspNetCompatibilityRequirements(RequirementsMode = AspNetCompatibilityRequirementsMode.Allowed)]
public class feedHandler
{
	[WebInvoke(ResponseFormat = WebMessageFormat.Json,
	BodyStyle = WebMessageBodyStyle.Bare,
	Method = "POST",
	UriTemplate = "/friendsfeed")
	]
	[OperationContract]
	public FeedResponse GetResponse()
	{
		return new FeedResponse
		{
			method = "multiFeedStory",
			content = new Content
			{
				feed = new Feed
				{
					template_id = "1234",
					template_data = new TemplData
					{
						swf = "",
						linktitle = "Louisefying",
						linkurl = "http://apps.facebook.com/louisefy/",
						images = new FeedImage[]
						{
							new FeedImage
							{
								src = "http://foo.bar/my.png",
								href = "http://apps.facebook.com/louisefy"
							}
						},
					}
				},
				next = "http://apps.facebook.com/louisefy",
			}
		};
	}
}

[DataContract]
public class FeedResponse
{
	[DataMember]
	internal string method;

	[DataMember]
	internal Content content;
}

[DataContract]
class Content
{
	[DataMember]
	internal string next;
	[DataMember]
	internal Feed feed;
}

[DataContract]
class Feed
{
	[DataMember]
	internal string template_id;

	[DataMember]
	internal TemplData template_data;
}

[DataContract]
class TemplData
{
	[DataMember]
	internal FeedImage[] images;

	[DataMember]
	internal string swf;

	[DataMember]
	internal string linkurl;

	[DataMember]
	internal string linktitle;
}

[DataContract]
class FeedImage
{
	[DataMember]
	internal string src;

	[DataMember]
	internal string href;

}

web.config:

<system.serviceModel>
	<behaviors>
	  <endpointBehaviors>
		<behavior name="Popcorn.feedHandlerAspNetAjaxBehavior">
		  <webHttp />
		</behavior>
	  </endpointBehaviors>
	</behaviors>
	<serviceHostingEnvironment aspNetCompatibilityEnabled="true" />
	<services>
	  <service name="Popcorn.feedHandler">
		<endpoint address="" behaviorConfiguration="Popcorn.feedHandlerAspNetAjaxBehavior"
		  binding="webHttpBinding" contract="Popcorn.feedHandler" />
	  </service>
	</services>
</system.serviceModel>

Server based real-time face detection in Flex

This post will demonstrate the feasability of face detection in web cam feeds grabbed by a flash/flex application. It’s inspired by a prototype of Martin Speelmans, informed by my work with Flash and web cams and my experiments with OpenCV. The basic premise is that a flex application running in a users browser grabs web cam shots, compresses them and sends them to a server. The server decompresses the picture, does face detection on it, and sends the result back to the client. All fast enough to give the user a relatively smooth experience. A fairly impressive Actionscript 3 face detection implementation exists, but my guess is that — barring a quantum leap in Adobe compiler technology — it’s gonna be a few years before fast, reliable Actionscript 3 face detection is feasible in Flash Player. Silverlight may be a different story, but it doesn’t support web cams yet.

The first prototype was implemented in Flash since I refused to program in XML (which you tend to to in Flex) as a matter of principle. When it turned out that Flash doesn’t support web services, I relented and changed to Flex. The parameter marshalling code that Flex Builder generates turned out to be too slow for low latency operation tough and was dumped in favour of a HttpService. The server part is implemented in ASP.Net, with C# calling EmguCV wrapped OpenCV. The code is at the bottom of the post.

The client goes through the following steps:

  1. Setting up the UI, getting the web cam running, setting up a timer to tick three times a second.
  2. On timer ticks, a shot is grabbed from the web cam.
  3. The picture is scaled to 320×240 pixels. The scaling is handled is by native library code and takes a few milliseconds.
  4. The picture is converted to grayscale. OpenCV facedetection only operates on one colour channel anyway and grayscale images compress better. The colour transformation is handled by more native library code and also takes just a few milliseconds.
  5. The picture is then PNG encoded. An encoder lives in the mx.graphics.codec namespace and at ~150ms for a 320×240 pic, it’s pretty fast. The resulting bytearray is around 60kb.
  6. The bytearray is base64 encoded which takes around 100ms.
  7. Finally the bytearray is sent to the server along with a sequence number. The server returns the sequence number so that the client can make sure it doesn’t use old, out-of-sequence results.

Upon receipt of a post, the server does the following:

  1. The request string is base64 decoded to a bytearray.
  2. A bitmap is created from the bytearray and made into a EmguCV grayscale image.
  3. The faces are indentified with a Haar Cascade detector
  4. The results, along with some performance information and the sequence number, are returned to the client as XML

Total server-side time is around 150ms with almost all of it spent in the face detection call. The client can do whatever it want’s with the face information — my demonstration projects a bitmap on top of detected  faces in the video feed. Total roundtrip time is less than half a second at three frames a second on a non-bandwith constrained connection in the same city as the server. This is probably enough to give relatively passive users the illusion of real-time face detection. I’ve also gotten positive reports from testers in the US where latency is higher.

I experimented with zlib compression instead of PNG encoding but the difference in both space and time was marginal (PNG uses zlib so that shouldn’t be too surprising). Instead of grayscaling the image, I also tried yanking out just one colour channel from the 32bit RGBA pixels, but iterating 320x240x4 bytearrays in Actionscript was dead-slow. Ditching http in favour of AMF and using AMF.Net or FluorineFx on the server may improve latency further.

What is point if all this you ask? A haven’t the foggiest idea really, but it’s good fun. You can certainly use it to create very silly facebook applications. You could conceivably use it to detect the mood of your users by determining whether they are smiling or not. Is this usable in a production scenario? Hard to say. The current server is a 3.5GHz Celeron D — a right riceboy machine. With one user hitting it, the CPU is at 20-30% utlization, suggesting it’ll tolerate a few concurrent users at most. Getting a proper machine and installing Intel Performance Primitives would probably help a lot. If you really meant it, you could run the OpenCV part on a PS3 or on a GPU.

Download the important parts of the code here.

Facebook signature generation in .Net

While the Facebook Developer Toolkit handles most of the needs of your average Facebook application, there is not support for the Post-Remove stuff that happens when users decide to remove your application. When your application is removed by a user, Facebook submits a “Post” in the the general direction of a url you’ve specified. The post contains a “fb_sig_user” with the relevant userid and the naive developer would remove this user from their database. That — however — would make the application vulnerable to an attack where a bad guy would hammer the post-remove form with request containing random userid, causing you to falsely believe these users have removed your application.

Below is some code that computes the proper signature that you can use to compare against the one Facebook sends along with the request. The crypto-parts were lifted from the guts of the Facebook Developer Toolkit. The process of computing the signature is described here.

public static string GenerateSignature(NameValueCollection formParams, string secret)
{
	string[] keys = formParams.AllKeys;
	Array.Sort(keys);
	string prefix = "fb_sig_";

	Dictionary dict = new Dictionary();
	var dictInit = keys.Where(k => k.StartsWith(prefix))
		.Select(k =>
			new { key = k.Substring(prefix.Length), val = formParams.Get(k) });
	foreach (var p in dictInit) { dict.Add(p.key, p.val); }

	var signatureBuilder = new StringBuilder();

	// Sort the keys of the method call in alphabetical order
	List keyList = ParameterDictionaryToList(dict);
	keyList.Sort();

	// Append all the parameters to the signature input paramaters
	foreach (string key in keyList)
		signatureBuilder.Append(String.Format(CultureInfo.InvariantCulture,
			"{0}={1}", key, dict[key]));

	// Append the secret to the signature builder
	signatureBuilder.Append(secret);

	MD5 md5 = MD5.Create();
	// Compute the MD5 hash of the signature builder
	byte[] hash = md5.ComputeHash(
		Encoding.UTF8.GetBytes(signatureBuilder.ToString().Trim()));

	// Reinitialize the signature builder to store the actual signature
	signatureBuilder = new StringBuilder();

	// Append the hash to the signature
	foreach (byte hashByte in hash)
		signatureBuilder.Append(hashByte.ToString("x2", CultureInfo.InvariantCulture));

	return signatureBuilder.ToString();
}

Here’s some code that uses the method:

string sig = GenerateSignature(Request.Form,
	ConfigurationManager.AppSettings["FACEBOOK_SECRET"]);
if (sig == Request.Form["fb_sig"])
{
	string fbuid = Request["fb_sig_user"];
	if (fbuid != null && fbuid.Length > 0)
	{
		// Remove user
	}
}

LinqtoCRM 0.2.5 released

A little over a week ago, I got a wonderful email from Mel Gerats. He’s implemented a bunch of new features for LinqtoCRM, including Count, Skip/Take, Contains, EndsWith, StartsWith. There’s also support for chained queries and for returning CRM entities as well as anonymous types.

Mel also found a way to decouple LinqtoCRM from the web service so that it can be compiled as a separate assembly. This comes at the cost of having to define types and relations in your own code however. I rather liked the lightweight approach of querying against the web service entities and will still work with the current release. Going forward, generating the necessary types from the metadata service with a CRMMetal tool (similar to the SQLMetal tool that LinqtoSQL employs) might be the right thing to do — especially because the intermediary entities used in N:N (many-to-many) relationships are not exposed in the web service. The other major thing that needs doing is a proper projection implementation permitting all kinds of expressions in the select part of queries.

Enough babbling, head on over to the CodePlex site for code and samples of use: http://www.codeplex.com/LinqtoCRM

Facedectection in C# with less than 50 LoC

I’ve been mucking around with face detection a bit lately. Here’s a short guide to getting face detection running in C# in a short amount of time.

UPDATE: Recommend EmguCV for C# wrapping OpenCV, read the updated guide.

I’ve identified two free computer vision libraries that do face detection:  Torch3vision and OpenCV(I’m sure there are plenty more, but these seem to be comprehensive, recently updated and freely available). Torch3vision claims to be better than OpenCV but on the other hand more people are building libraries and wrappers around OpenCV and there’s even a wrapper for .Net. While it doesn’t yet wrap the face detection components of OpenCV, it seems to be the most promising solution.

To get face detection in OpenCV to work with C#, do the following:

  1. Install OpenCV and OpenCVDotNet as per the instructions
  2. Get CVHaar.h from this discussion and place it in C:\Program Files\OpenCVDotNet\src\OpenCVDotNet UPDATE: Dud link, read the updated guide
  3. Open OpenCVDotNet.sln, add CVHaar.h to the solution and include it in OpenCVDotNet.cpp
  4. Rebuild the solution
  5. Create a Windows forms application as described in the tutorial, but do something like the code below
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using OpenCVDotNet;

namespace opencvtut
{
    public partial class Form1 : Form
    {
        private CVCapture cap;
        private CVHaar haar;

        public Form1()
        {
            InitializeComponent();
        }

        private void timer1_Tick(object sender, EventArgs e)
        {
            using (CVImage nextFrame = cap.QueryFrame())
            {
                Rectangle[] faces = haar.detectPatterns(1.3, nextFrame, 20, 20, 1.1, 2, 1);
                for (int i = 0; i < faces.Length; i++)
                {
                    nextFrame.DrawRectangle(faces[i], Color.Yellow, 3);
                }
                pictureBox1.Image = nextFrame.ToBitmap();
            }
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            // passing 0 gets zeroth webcam
            cap = new CVCapture(0);
            haar = new CVHaar(
                "C:Program FilesOpenCVdatahaarcascadeshaarcascade_frontalface_alt2.xml");
        }
    }
}

Happy detecting 🙂

Microsoft CRM 3.0 32 bit to 4.0 64 bit

Last week I helped a client move from CRM 3.0 32 bit to CRM 4.0 64 bit. Note that 3.0 never came in a 64 bit version so the 32->64 bit upgrade has to happen on the 4.0 side. The procedure described below assumes the existence of a 32 bit staging server to keep the production environment running during the upgrade but it is not strictly necessary.

  1. Backup/restore the 3.0 32 bit database to the staging server
  2. Install 3.0 on the staging server, instructing the installer to use an existing database. Point it at the database you just moved (I highly recommend consulting the redeployment tool at this stage, as getting the databases right is rather hit ‘n miss)
  3. Upgrade the staging server to 4.0 32 bit
  4. Install 4.0 64 bit on the new production server, don’t worry about creating a default organization, you can remove it later on
  5. Backup/restore the 4.0 32 bit database to the new 64 bit production server. Note that you can’t use detach-attach to move from 32 bit to 64 bit — attempting this will bork the database
  6. Use the 4.0 deployment manager “Import organization” feature and point it at the database you just moved
  7. Make the newly imported organization the default one
  8. Depending on the extend of the customizations to the 3.0 installation, some fiddling may be required to get everything running on 4.0

That’s it! And there wasn’t but a single import/export customizations step. The new “Import organization” feature in the 4.0 deployment manager is an absolute killer for this sort of mucking around — use it.

Links:

Playing Pong with your shadow

The technical stuff from the Living Room of Map_of_You was exhibited at the afterparty of the it-natten event at ITU. Instead of moving around furniture-icons, you could play Pong with your shadow. I purchased a Logitech Quickcam Pro 9000 for the event, a superb piece of kit. So superb, in fact, that it proved impossible to run the installation with a white background because the camera would see the all-white screen and try to colour-correct out something. I ended up running the thing with the alpha-channel (normally used for tuning) displayed in all it’s pixelated CGA-glory. It was supposed to be a geeky/techy anyway, so that was OK. An automatic AI-mode, a scoring mechanism and sound would have been nice.

People genuinely seemed to have fun though, and I got a chance to explain how the setup works to a few of the high school kids there, hopefully getting them interested in a career in IT. Pictures below, courtesy of Mette Lundberg.

it-nat1

it-nat2

it-nat3

.Net/Firefox Screen Scraping

Need to scrape a website? I have two links for you:

Solvent from the MIT SIMILI project. In combination with Piggy Bank it’s a scraper on it’s own, but I only use for its superb XPath generator. Just activate the sprayer and click on an element you want and Solvent will generate an intelligent XPath expression to get at it. Solvent will also higlight other elements on the page that would be returned with by the query and you can even dynamically edit the expression to narrow or broaden the result. All visible right there in the browser window.

Now switch to Visual Studio and Html Agility Pack, a great project that lets you parse HTML documents and query them using XPath just like they where XML. Solvent and Html Agility Packs (HAP) perception of the the DOM may sometimes differ slightly but, with a bit of tweaking, the visually generated XPath from Solvent works just great with your HAP code.

Truly a match made in heaven…

Older Posts Newer Posts