From: MikkelFJ <mikkelfj-anti-spam@...>
Date: 2002-12-12T09:22:43+09:00
Subject: Re: functional programming "style"


"Martin DeMello" <martindemello@yahoo.com> wrote in message
news:FKOJ9.205315$ka.4793771@news1.calgary.shaw.ca...
> MikkelFJ <mikkelfj-anti-spam@bigfoot.com> wrote:
> > 8-Queen happens to be a nice pattern to sample pixels in, but
>
> Interesting! Could you point me somewhere for details?

I think I recall having seen n-queen sampling in litterature, but it may
also be my own invention.

An image is divided into blocks of n by n pixels. n-queen sampling samples n
out n^2 pixels in each block.

The following is from my own experience only - the n-queen pattern has the
nice feature that the pattern resembles a random pattern which is generally
a good way to sample (good coverage and avoids apparent aliasing effects),
yet you know exactly what pixels have been sampled. You can rotate the
pattern such that you get 100% sample coverage after n iterations.

The reasons I worked on this was as follows (based on flawed recollection):
- some years back at university we had a 9 man large group that should
develop various software for controlling a robot arm remotely via network.
The system had visual feedback and estimated wireframe model of robot.
The controlling computer in the robot room was not very fast. It should
manage robot control, video capture and network communication over limited
bandwidth. Although the plan was to use standard video compression such as
mpeg, but we realized we had to invent our own method to meet these
criterias of fast low bandwidth compression and because the OS/9 operating
system made it difficult to pick useful software off the internet which was
not as vast as now. Later that task might have been solved by VNC, more CPU
and more bandwidth.

We decided that a robot image is mostly static except where the robot arm
is. Therefore you need to identify motion and only ship those image blocks
containing changes. How do you detect changes fast? You sample selected
pixels in a pattern that gives good coverage. This allows you to scan n
times faster than otherwise, and still guarantee 100% change detection once
the image is complete sampled (or not quite, as the live image may have been
resampled meanwhile). We developed a simple point system for each block that
involved the amount of change and how long time had passed since last
change. Then for a given bandwidth we selected as many blocks as possible
and transmitted those, resetting their block score to zero. In order to
avoid sorting blocks for selection we created a crude priority list where
iterated over the block score table and scoped all blocks above 'threshold'.
Then we halved the threshold and repeated until we had enough blocks to
transmit.
In this way we could very quickly detect change and simply transmit as many
blocks as possible while dynamically being able to tune the bandwidth
consumed. We didn't try to compress transmitted blocks, but that could also
be done - we assumed the CPU would probably be better used by making block
sizes smaller decreasing n in the n-queen pattern.

One interesting aspect of the algorithm is the exploitation of how the brain
works: The brain tracks motion and completes motion even when information is
absent. Thus it would be sufficient to give the brain hints about the motion
in order to establish realtime feedback. The quality is obviously depending
on how much bandwidth could be provided.

I have some C-source for the image compression - I haven't looked at for
quite a while - is quite small.

Mikkel