Applications of UD (part II)

I am continuing the post Applications of UD by two comments, one concerning Google, the other Kinect.

Google: There are many discussions (on G+ in particular) around A second spring of cleaning at Google, mainly about their decision concerning Google Reader. But have you notice they are closing Google Building Maker? The reason is this:

Compare with Aerometrex, which uses UD:

So, are we going to see application 2 from the last post (Google Earth with UD) really soon?

Kinect: (I moved the update from the previous post here and slightly modified) Take a look at the video from  Kinect + Brain Scan = Augmented Reality for Neurosurgeons

They propose the following strategy:

  • first use the data collected by the scanner in order to transform the scan of the patient’s brain into a 3D representation of the brain
  • then use Kinect to lay this representation   over the real-world reconstruction of the patient’s head (done in real time by Kinect), so that the neurosurgeon has an augmented reality representation of the head which allows him/her to see inside the head and decide accordingly what to do.

This is very much compatible with the UD way (see application point 3.)  Suppose you have a  detailed brain  scan, much more detailed than Kinect alone can handle. Why not using  UD for the first step, then use Kinect for the second step. First put the scan data into the UD format, then use the UD machine to stream only the necessary data to the Kinect system. This way you have best of both worlds. The neurosurgeon could really see microscopic detail, if needed, correctly mapped inside patient’s brain. What about microscopic level reconstruction of the brain, which is the real level of detail needed by the neurosurgeon?


22 thoughts on “Applications of UD (part II)”

  1. Aerometrex have prerendered graphics, polygon and point cloud sequences. I think Euclideon need more than 1 customer to have a breaktrough with their proprietary software.

    1. John, that’s boring. First is surely a scam, now it’s only one company using it. That’s cheating by moving the posts during the game. What I believe is that UD is surely not a scam and also that it’s first applications will be not in the game industry, but as a tool for understanding spatially organized information. For my side, Google Earth is far more important than the latest game, likewise for the medical applications. But I’m a geek.

      One more thing: I don’t even care about the euclideon company, mainly because I don’t approve unnecessary secrecy. But, ironically, here is what I think is going to happen (and I don’t think you shall understand completely). That’s totally speculation from my part, take it as a pamphlet! Some smart google guys will get cured from the cartesian disease and they shall somehow write their own UD algorithm, without buying it from Bruce Dell. Then they will use their UD algorithm for Google Earth (see also Google Lat Long) and everybody will be like “AAAH”, “OOOH” that’s great, how smart are they. Then, Bruce Dell will tell everybody how it’s him who invented the whole thing, but everybody will tell “so what? OK, you had a nice amateurish idea (in fact what are you, what’s your training?), but you cannot possibly claim you’re better than GOOGLE”. “No! I don’t claim such a thing, but you see, when I proved you the first time that it’s possible, you said that’s a scam”. “OK then, show us the patent for UD”. “Well, apparently is hard to patent a piece of geometrical thinking” Bruce Dell could possibly reply. That’s the world.

      Unless Bruce Dell makes open source his UD now, before somebody reinvent it. (Some) money or fame, what will it be?

  2. It’s natural that people call it scam if it’s a lot of bragging and secrecy going on. If Bruce doesn’t give credits/refer to any sources, I think nobody would bother to credit him either. Together we will make progress.

  3. Hi Marius, i am hoping you will create the algorithm and open source it here. That’s why i come to your blog everyday 🙂

    1. Hi Tony, thanks for passing by. We have a saying here, I don’t know how to translate it better, it’s that’s nothing better than what’s done by one own hand. I have a solution, I think (and I’m in doubt because it’s not yet clear to me if the proof of O(log N) is OK), but I have not tried to write the program because I assumed that some clever hacker out there could easily do better. So, on one side I iterate my call (and Tony’s) for a working program or a rigorous math proof! On the other side I shall take your message as a challenge and I shall try to write the program (this means realistically several months of trying, from the proof to the product). I kind of not believing that until now nobody in this big world managed to write one, come on people, it’s almost clear what to do. Me too, I was hoping that any day will bring some message with a full solution. This blog is a tool for achieving several goals and openess is one of them.

      1. Marius, I wait for read you idea, code is not hard, new ideas is hard. One incomplete and simple idea can evolve .. one implemetation generally not…

    1. OK, I’ll give a try, let me think how we could do this in the most open way. Maybe is a bad idea, but at some point it would be good to have a “Lena” equivalent for this problem, i.e. a reference database which could be used to asses the performance of different approaches. Let me think what to do, UD has not a high priority on my list, although in this fast shifting world it might happen that continuing into the academia is not a creative enough idea.

      1. I can’t describe it until I try it in practice, it may well happen that O(log N) could mean a huge constant multiplying log N, therefore in practice this could mean the algorithm (second part) is slow. Therefore I have to try it, also I have to write and put on arXiv the proof, which can be of independent interest. That’s one thing, meaning in particular for me to really explore what has been done in this field, because the solution is interesting, but somehow elementary (explaining how was possible for somebody, like Dell, to be able to rediscover the main ideas from that field and then to get to a new fundamental idea, alone). I can’t do it otherwise, it would not be professional. The second thing is that my initial interest for UD came from seeing it as a potential example of computing with space. Although I mailed twice Bruce Dell to ask him for the mathematical background of the algorithm, without reply, I feel that it would be only fair either Dell to make public his solution, or some smart (group of) people to arrive at an open source solution. This second part would be, for me, the best thing, because I would not have to learn fast yet another field, discovering maybe that the idea was already present in some old papers, spending again a lot of time to convince narrow specialists that they don’t quite explored well their field, going again into controversies and so on. So, in conclusion, let me think what to do, because I gave all the hints for the solution already. Maybe, besides the posts on UD, this post is relevant also: Combinatorics versus geometric…, look also more attentively for the geometric equivalent of a positional numeral system (for example octrees can be seen as one, but with unnecessary constraints), maybe google for “signed-digit number systems” or “redundant number representations” or “carry-free addition”. Then think that you have to transform the 3D points database into a dictionary (octrees do such a thing, right?), such that, as Dell said repeatedly, the algorithm for finding the relevant 3D atoms becomes like a search in a dictionary, instead of ray-casting (although it is a solution for the ray-casting problem). I don’t know if my (partial! unverified!) solution is the same as Bruce Dell’s.

  4. Lets say an aerial animation is 1920×1080. Its painting 2,073,600 pixels. Could the search algorithm be just rendering one line of new 1920 pixels as it comes in and clearing memory of the top 1920 going out. The rest are moved. Same goes for the 1080 line. Whichever the direction of the animation goes. This would not take into consideration of, for example a ground object’s lighting changes that would occur and show perhaps if the aerial was a video. Perhaps the algorithm checks the texture map for lighting changes and the engine renders accordingly.

    1. Shading, lightning, etc, are not part of the UD problem. In fact UD has two parts: (1) give an algorithm which takes as input a database of N 3D points with qualities (color) and which outputs (with no time constraints) a database which is not larger than the initial one, i.e. O(N) in memory space , but which allows to use later … (2) an algorithm which search in realtime (i.e. O(log N) or maybe O( (log N)^2) in time) in the processed database and gives only the relevant 3D atoms needed further. Once you have those, you already passed the computational bottleneck and you can do the rendering at your leisure. The thing of UD is how to do (1). You are right, I think, that a good strategy for the algorithm from (2) would be to use the data (i.e. the visible 3D points) at moment t in order to alleviate the search demands at moment t+1.

      UPDATE: notice however that “t” and “t+1” are not times, properly, but places, POVs. If you stay still, you don’t need to run the part (2) of the algorithm.

  5. Yes I left Z rendering out on purpose. I was only thinking top down flyover. 5-20% of the data is an important factor. Sorry my knowledge of math and programming is very basic. Most of what i say will probably be very obvious. However I have been known to get lucky from time to time 🙂

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s