Academic Facets: News and Views from Spatial's University Community

[#1]

My week has been dominated by the submission of a research proposal which, as any academic will tell you, becomes an “all consuming” process as endless financial approvals are needed before  the submit button can finally be pushed. However I’ll spare you the details and tell you about the idea behind the proposal.

For several decades now a large amount of CAM/CAM research has been motivated by the desire to get computers to “understand” 3D models, so like humans, they can recognise patterns and similarities in shapes. Over the years people have tried many different computer algorithms for analysing the faces and edges of B-rep models to determine if, say, a depression exists. Although specific problems (i.e. round holes) have been solved no general approach has immerged. The vagueness of the specification for shape properties like “thin walls” and “largely symmetrical” and the infinite variety of geometry combine to make the problem awfully difficult.

 
However maybe a new approach is feasible, maybe an automated solution is not the only answer? Perhaps tasks like feature recognition and similarity assessment could be done by Crowdsourcing based HITs rather than C++ computation.   A bit of background before I try and describe how…….

Wikipedia defines Crowdsourcing, as “a neologism for the act of taking a task traditionally performed by an employee or contractor, and outsourcing it to an undefined, generally large group of people, in the form of an open call.” A Human Intelligence Task (HIT), on the other hand, is a problem that humans find simple, but computers find extremely difficult. For example a HIT related to a photograph could be: “Is there a dog in this photograph?”  The two ideas can be combined so that large numbers of people are asked to do tasks “computers find hard”.

The Crowdsourcing approach to HITs is exemplified by Amazon's “Mechanical Turk” (mturk.com) site that provides an online marketplace enabling computer programs to co-ordinate the use of human intelligence to perform tasks which computers are unable to do. Requesters, the human beings that write these programs, are able to pose tasks known as HITs (Human Intelligence Tasks), such as choosing the best among several photographs of a storefront, writing product descriptions, or identifying performers on music CDs. Workers (called Providers) can then browse among existing tasks and complete them for a monetary payment set by the Requester (Amazon gift vouchers or cash).

Mturk has demonstrated a feasible way of providing cheap, robust, content based, Image analysis. Most days on the mturk site one can find Image analysis jobs requiring that the “edge of the road” or “road signs” be identified in urban photographs. Having lived in close proximity to various researchers who have grown old trying to workout “if the photograph contains a dog”, I thought this was a really neat idea. Possibly it could be seen as cheating, or simply giving-up, but either way it provides a solution and allows everyone to move on!

So our proposal is seeking funding to investigate if a similar approach can be used to solve the geometric reasoning problems found in Mechanical CAD/CAM.

How would this work for CAD/CAM? Well consider 3D Search Engines where the dream is that you upload a model as a query and get back a collection of the most “similar” parts in the model data base. But of course defining what makes two shapes similar is difficult, if not impossible, especially if the judgement has to be made purely on the basis of geometry. A few years ago we went through an exercise of manually classifying  a collection of 3D shapes and this produced pairs of objects with similarities judged as a % (if all the humans doing the classification agreed the two objects where similar then they were ranked as 100% similar). The results (shown here) were thought provoking because many of them identified relationships that would defy computation (not least because the people doing the comparison were engineering students who brought an implicit understanding component function to the task).

So our proposal is to simply Crowdsource the shape similarity problem as HITs, effectively showing pictures of the shapes in question to lots of people and asking them to select the most similar components. You get your data base of shapes indexed and they earn a few cent.

An obvious question is: “why would any one want to search a CAD databases for similar parts?” An academic answer would talk about “design reuse” or even “remanufacture” and “not reinventing the wheel”. Indeed one academic study by Berchtold into the use of a 3D database of "plastic clips" in a single automotive supply business reported that:

“Finding all similar parts for a given query part is the key to cost reduction. The potential cost savings to the company are in the range of $1 to $5 million a year.”

 However a brutally practical answer is that many companies would like to purge their databases of duplicate components (i.e. same shape different part number).  Could Crowdsource be a robust way of dealing with such problems …..if we are funded I’ll let you know next year…..