The Message-Only Architecture

 

OK, I've barely got twenty lines of code into this grand project so far, and it's already time to re-architect!

What I showed last time was the same architecture I have been using since Dinosaurs Roamed the Earth. It works like this: 

• You define a data structure that represents the problem space.
• You write a New function for the data structure. 
• You write a bunch of functions that operate upon that data structure.
• Each function takes a pointer to the data structure as its first argument.
• The main program creates the structure, owns it, and operates upon it.
  
• You keep getting older until someday you don't.

When I re-re-(re-?)started Tachyon recently, this was the style I automatically used, as a dog returneth to its vomit. Now, before we go too far in this well-trod path I want to recall that I have recently learned a new style and a better, thanks to the fabulous mechanisms for threading and communication of the fabulous new language C-2012, sometimes also called "Go"! Let us take a road less traveled by, for that will make all the difference. Because you've been down there, Neo. You already know that road. You know exactly where it ends. And I know that's not where you want to be. We have come to a fork in the road. Let us take it.

The new style that Go has taught me is this:

• Instead of a data structure, we have a running goroutine.
• Instead of fields in a data structure, we have local variables in the running goroutine.
• There is exactly one function call. It starts the da-    Look at that. I started typing "data structure". Wake up, Neo.      The single function starts the goroutine running, and returns the channel that it is listening to.
  
• All further requests that you can make of the goroutine are made through that channel.
• Sometimes you can pass in your own channel as part of a request. That is your reply-to channel, where the goroutine will send its response to your request.

Here's what it looks like in code:

 (from checkin e39407fd55986f916308a86ebcf11333039cc793 )

Here's the only public function:

func Start_Bulletin_Board ( ) ( Message_Channel ) {
  requests := make ( Message_Channel, 5 )
  go run_bulletin_board ( requests )
  return requests
}

It creates the requests channel, passes that to the goroutine, and passes the channel back to the caller.

Here's the run function:

func run_bulletin_board ( requests Message_Channel ) {
  bb := Bulletin_Board { output_channels : make ( map[string] []Message_Channel, 0 ) }
  for {
    msg := <- requests
    fp ( os.Stdout, "MDEBUG BB |%#v| gets message: |%v|\n", bb, msg )
  }
}

And here it is being used in main() :

  bb_channel := t.Start_Bulletin_Board ( )

  for {
    bb_channel <- msg
    time.Sleep ( 2 * time.Second )
  }

No race conditions in accessing the fields of a structure, in spite of arbitrary extensibility. This goroutine can be used by any number of other routines.

This is a beautiful style and it's going to change everything.

Starting Implementation

 

OK, so let us begin implementation, and let us promise (this time) to Keep It As Simple As Possible. Never implement any complexity because you think it might be important later. Only implement complexity when it is clearly needed to achieve the next goal.

 

So what's the first goal? I want a Message structure, and a Bulletin Board.

I want a nice general message structure that can do about anything, and I think this is it:

type Message map [ string ] interface{}

That's a bunch of names where each name is associated with anything at all. Ah, but how does the receiver interpret those anythings? The message must have a type. Let's just make that a string, too.

 

      type Message struct {
     Type string
     Data map [ string ] interface{}
   }

OK, that's better. Now the idea is that any receiver that knows this message type will also know how to interpret all of the values that the Data map contains.

So, what is the Bulletin Board?

Right now it is just a place for Abstractors to store their output channels. Every time an Abstractor starts up it will present its output channel -- the channel on which it sends the Abstractions it produces -- to the BB, and the BB will store it.

Here's a message channel:

type Message_Channel chan Message

 

And here's the initial implementation of the Bulletin Board:

type Bulletin_Board struct {
  message_channels map [string] []Message_Channel
}

For each channel-type (which is the same as the type of the messages that flow through it) the BB stores an array of channels. This is because there may be multiple Abstractors putting out the same message type.

And now we can write the BB's Register_Channel function.

func ( bb * Bulletin_Board ) Register_Channel ( message_type string, channel Message_Channel ) {
  bb.message_channels[message_type] = append(bb.message_channels[message_type], channel )

  fp ( os.Stdout, "BB now has : \n" )
  for message_type, channels := range bb.message_channels {
    fp ( os.Stdout, "    message type: %s     channels: %d\n",  message_type, len(channels) )
  }
}

Yeck. I guess it's not going to be very nice to paste much code here.

Well, you can see the code by cloning: 

     https://github.com/mgoulish/tachyon 

and looking at commit:

     0755cf718c71d296d29e314778a67fb5740f0ff3

From main (for now standing in for an Abstractor) we can now do this:

  bb := t.New_Bulletin_Board ( )
 var my_output_channel t.Message_Channel

 bb.Register_Channel ( "my_type", my_output_channel )
 bb.Register_Channel ( "my_type", my_output_channel )

and get this output:

BB now has :
    message type: my_type     channels: 1
BB now has :
    message type: my_type     channels: 2

So!  That's a start.

Hello, World!

OK, so it's time to make a real system, a beginner's system, and see if we can get it to exhibit any interesting behavior at all. We will describe a simple perceptual scenario, and then describe the system behavior we would like to see in response to it. 

This story-telling post will be the last step before beginning real implementation.

 

The Perceptual Scenario

Let's make this Real Easy. We have a perfectly motionless star field, and an asteroid traversing it. The asteroid is easily visible: a medium-bright spot three pixels across. And it is traveling slowly: five pixels per frame. 

The top-level goal is to identify the asteroid in every frame, and build an abstraction that links all those instances of the asteroid together. That is, the top-level Abstractor recognizes that the sequence of asteroid appearances in the sequence of frames are all the same object. It ties them together in a data structure and tells us the direction and velocity of the asteroid's movement.

The System Scenario

How should the system behave in response to the above perceptual scenario?

• The sensor starts firing, producing an image every second.
  
  
• The THRESHOLD Abstractor fires, and produces a reasonable threshold for binarizing the image.
  
  
• STARS takes the threshold and uses it to produce a list of star-like objects. This list includes information like centroid, diameter, and total energy.
  
  
• BLINKER looks at sets of results from STARS, for example in bunches of 5 at a time, and looks for out-of-place objects. It will report on objects that are in a particular location in frame N, but were not there at N-1. It will also report on objects that were in a particular location at frame N, but are no longer there at N+1.
  
  
• ASTEROIDS uses the data from BLINKER to construct sequences of locations that it believe to be consecutive images of the same object. It concludes its abstraction when the object departs the camera's field of view. This is the top-level goal of this system. When we produce one such Abstraction, the system shuts down.
  

 

What interesting behavior will we see?

In keeping with the idea of starting out small, we want this demonstration to exhibit only a single interesting property of the eventual system. Namely, one of the pillars of an intelligent system: self-organization. The sequence of events outlined in The System Scenario, above, will not be hard-wired into the system at programming time, but rather created during run time.

How will that work?

 

1. The Bulletin Board gets instantiated before anything else. It is an independently running goroutine. All Abstractors know how to talk to it.
   
   
2. The Sensor will start firing as soon as it is created, because that's what Sensors do. It takes a major intervention by a high-level control system (which we do not have yet) to get a Sensor to stop firing.
   
   
3. All the other Abstractors, when they are first instantiated, send Work Requests to the Bulletin Board. These are Messages, like everything else, so their format is very extensible. In the future these Work Requests will be able to express much more specific kinds of work. But for now, they only say "I want images", "I want thresholds", "I want stars" -- things like that.
   
   
4. After sending out their own work requests, the non-Sensor Abstractors also start perusing whatever Work Requests the Bulletin Board has. When they fins one that looks interesting, they send out a Work Offer in response -- and it gets accepted. Soon the system has wired itself up at run-time, and starts working as outlined the The System Scenario.
   
   

OK, so in this example the Work Requests and the Work Offers are pretty trivial, and don't really give us anything more interesting than hard-wiring at programming time would. But the hope is that this provides a foundation that we can elaborate later to yield much more interesting runtime behavior.

This sounds like a plan.

Let us begin.

A Self-Altering System

Some sources of variable behavior in this architecture are Abstractor parameterization, alliance-forming, and reproduction.

Two different instances of a given Abstractor type can show very different behavior based on different parameterization. Larger-scale changes in system behavior will result from varying the Abstractor chains that come together to create the top-level Abstractions.

Somehow these two sources of variable behavior must be made to operate spontaneously, without programmer intervention. But how?

 

Parameterization and Inheritance

Parameterization is the initial set of variable values that an Abstractor is instantiated with, plus more values that it learns during its processing career. The values of this set of variables determines how the Abstractor processes its data, and how it behaves in the marketplace -- possibly how it decides to reproduce? All of these values are subject to change by the Abstractor itself as it gains experience processing.

If an Abstractor reproduces, the daughter Abstractor will begin as a clone of the parent with the same paramaterization that the parent has at the time of reproduction. Strictly Lamarckian. 

The daughter will then begin its own career, probably diverging from its parent as it progresses.

Some examples of Abstractor parameters:

• A low-level region growing Abstractor has a parameter that controls how large a gap can exist between two foreground pixels for them to still be considered part of the same region.
  
• An object tracking Abstractor has a parameter controlling what type of region growing Abstractor it will use during periods of high-noise images.
• An Abstractor has a parameter that controls its economic risk-taking behavior in situations where it has the choice of investing its own savings to produce an Abstraction in the hope of receiving payment.

 

Searching Parameter Space

If an Abstractor has, for example, five parameters that control how it applies its algorithm to its inputs, you can understand those five variables as its parameter space. Any particular parameterization is a point in that space. It is likely that only a small fraction of the entire possible parameter space will produce useful results.

When a parentless Abstractor first begins working, it does not know what region of its parameter space will yield useful results, so it will start a searching through its entire parameter space. 

What it's searching for is a region of parameterization space that produces meaningful results. An Abstractor can make its own judgments about what results are meaningful. For example, an Abstractor that finds foreground and background regions in a binary image knows that it does not have a meaningful result if it has classified the entire image as a single region. The Abstractor may even have a metric that allows it to judge some results as better than others. For example an image thresholder may prefer a threshold that is near the middle of a region of grayvalues over which the foreground area of the thresholded image shows little change.

But the results that an Abstractor judges to be meaningful are not necessarily useful to higher level Abstractors. To learn the needs of its prospective customers, the Abstractor will have to take its best guess, create its Abstraction, and then submit it to the judgement of the market. What it then learns from the market will constitute a new phase of narrowing its parameter space in the Abstractor's attempt to become profitable.

If an Abstractor has, for example, five parameters that control how it applies its algorithm to its inputs, you can understand those five variables as its parameter space. Any particular parameterization is a point in that space. It is likely that only a small fraction of the entire possible parameter space will produce useful results.

When a parentless Abstractor first begins working, it does not know what region of its parameter space will yield useful results, so it will start a searching through its entire parameter space. 

What is it searching for? A region of parameterization space that produces meaningful results.

 

Alliance-Forming

Costs and rewards imposed by the Market drive alliance-forming behavior among Abstractors. There will probably be small costs associated with inspecting potential inputs, but the largest costs incurred by Abstractors is the creation of Abstractions 'on consignment'. These are Abstractions that are created without any certain customer and sent to the Bulletin Board in the hope that they will find use in some higher-level work and thus be paid for. Because it must defray the costs of speculative Abstractions, an Abstractor must charge higher prices for those which are accepted.

But Abstractors strive at all times to maximize profit, and a large component of that effort is cost reduction. A great way to reduce cost is to produce more of what your customers want to buy, and less of what they don't. When an Abstractor gets paid for some of its work, it will produce more work like that in succeeding frames.

What is 'more work like that', exactly? Probably a region of the Abstractor's parameter-space.

Alliances form from both ends. When higher-level Abstractors find suppliers that they like, they start checking those suppliers first. When lower-level Abstractors notice that they are getting paid for particular results, they will narrow their search window to focus on the types of results that are getting bought. This allows them to produce results less expensively, which means they can maintain their profit margin while reducing prices. They can also accept a lower profit margin when they have a higher expectation of frequent business. Lowering prices makes them still more attractive to their higher-level customers, and an alliance has formed.

 

An Example of Shifting Alliances

Let's say we have an Abstractor that is designed to track a tumbling asteroid across a time-sequence of images. It buys Abstractions from a region-growing Abstractor and looks for regions that are moving smoothly across the stack.

At first the asteroid is well-lit and the region-grower has no trouble seeing it in each image. The tracker is happy because it finds the asteroid in each image, always the same delta from one image to the next. It gets to put out high-certainty Abstractions that get bought for a good price. Life is good.

But, alas, the Tracker's happiness is soon to fade.

As the asteroid continues to rotate, it begins to occasionally show a face that is covered with some dark stuff. So dark that the faint dot of the asteroid in our images becomes occasionally invisible for a few frames at a time.

The Region Grower is no longer able to locate the asteroid in all images, so the Tracker is no longer able to create a high-certainty sequence across each stack of images. Because it is no longer able to post high-certainty results, its customers become unhappy. They cannot afford to pay as well for low-certainty results.

So! The Tracker starts to look for a new supplier of region-growing, specifically for the images in which the asteroid has not been found. It advertises its desire for region-finding work to be done on specific small squares of the troublesome images, where it calculates the asteroid ought to be.

This advertising of a request for work gets the attention of an exotic region-grower that uses non gray-values but noise analysis to find regions. Attracted by the Tracker advertisement, it tries its technique on the images in question and succeeds! It finds regions in which the distribution of gray-values has a significantly different standard deviation than does the general background.

When the Tracker sees these new results, it finds that the new region-grower has found regions in just the expected places, and of the expected size. It pays for the work, and a new alliance is formed.

If the asteroid comes to a time when it is once again easy for the grayvalue region finder to provide all results, Tracker will stop using the more expensive exotic region finder. But if at some point the bad images return, it will remember whom to call.

Market forces are central to adaptation

I have thought about adding market behavior to Abstractors for a long time, but I have always thought of it as a bit of a frill. Maybe a way to make the system use less resources, but nothing more.

Now I see that, for intelligent behavior to emerge from a complex system, you need more than simply many interacting agents. You need some force that makes the many interactions tend in adaptive directions.

That force is supplied by the Market.

 

 

Everything is a Message

On further reflection, I like this generic-map structure so much that I'm going to use it for everything. Every message that is sent anywhere in the system will be of that form. In fact, I will call the basic data structure a "Message".

 

type Message map[string]interface{}

 

And all the different specific data types will just be defined as specializations of that type:

    

type Abstraction      Message

type Work_Description Message

 

The differences between the various specialized messages will be that they have different 'mandatory' fields, which will be filled in by their creation functions:

   

func New_Abstraction() (Abstraction) {
  return Abstraction { "type"    : "abstraction",
                       "id"      : 1,
                       "version" : 1,
                     }
}

Why use such a generic structure for everything? Because I want this system to be able to run forever, with different Abstractor types getting added to the system, with old Abstractor types getting upgraded -- all without ever needing to shut down to recompile all the code.

If you used 'normal' data structures, you would have to shut down and recompile every time a new data type were added to the system.

You might not even be able to get to all the code! At first every Abstractor in this system will be a goroutine and they will all be running in a single process. That would probably work well enough to use most of the computing resources of one large box. But later it would be easy to add a portal so that Abstractors running in a separate process, or even on a separate box could become part of the system, and then you would be running a single system across the internet.

The system gradually evolves, either because human programmers are adding new Abstractor types and new Abstraction types, or because we find some way to add those automatically. And there is never any need to stop anything while the system evolves. The new Abstractors just show up and start talking to the Bulletin Board, and everything else keeps working.

You could even add new fields to a given Abstraction type without damaging old Abstractors that use that type. They simply don't use the new fields, but can keep using the old fields the way they always have done.

Imagine this: 

You have a bunch of vision systems that are bulldozers -- or something -- collecting regolith from the surface of an asteroid. (Do asteroids have regolith, like the Moon?) And they keep getting into some kind of trouble in certain situations. They are having vision system failures once in a while that require expensive -- and slow -- human intervention. 

So the vision engineers spring into action. They take a look at the stored image sequences from when the bulldozers got into trouble and they say "Oh, I see what's happening. Wow, we never thought of that!" And they write some new Abstractors that will detect just that special trouble-making situation and respond to it. 

The new code gets transmitted to the bulldozers. The code gets launched as a separate process that knows how to use inter-process communication to become part of the running system. No need to shut anything down.

The upgraded bulldozers quit having that particular problem.

Or maybe, somehow, those new Abstractors get invented automatically.

Either way, we have a vision system that can change or add to the code it's using, adapting to new or unanticipated challenges, without ever shutting down.

Just like you!

Here's a complete little example program, showing Messages getting specialized into Abstractions and Work_Descriptions:

// start of code

package main

import (
         "os"
         "fmt"
       )

var fp=fmt.Fprintf


type Message map[string]interface{}

type Abstraction      Message
type Work_Description Message


func New_Abstraction() (Abstraction) {
  return Abstraction { "type"    : "abstraction",
                       "id"      : 1,
                       "version" : 1,
                     }
}


func New_Work_Description() (Work_Description) {
  return Work_Description { "type"    : "work_description",
                            "version" : 1,
                          }
}


func Print_Abstraction ( a Abstraction ) {
  fp ( os.Stdout, "Abstraction: |%#v|\n", a )
}


func Print_Work_Description ( wd Work_Description ) {
  fp ( os.Stdout, "Work_Description: |%#v|\n", wd )
}


func main () {
  a := New_Abstraction()
  Print_Abstraction ( a )

  wd := New_Work_Description()
  Print_Work_Description ( wd )
}

// end of code

And the output :

 

Abstraction: |main.Abstraction{"id":1, "type":"abstraction", "version":1}|
Work_Description: |main.Work_Description{"type":"work_description", "version":1}|

But if you try to pass an Abstraction into the Print_Work_Description() function, you get:

 

cannot use a (type Abstraction) as type Work_Description in argument to Print_Work_Description

An Architecture for Machine Vision

It has seemed to me almost axiomatic for some time that 'intelligence' can only be an emergent property of systems made of many independently operating actors, cooperating, competing, and communicating.

The ideal place to test that concept is in the realm of visual perception.

 

 

Machine Vision is not computer programming

In normal computer programming, the problem domain is completely understandable. If, for example, you are writing a web server, you can go learn all there is to know about the HTML 2.0 specification. HTML 2.0 is a finite logical system created by humans. So is the internet. So is the Transmission Control Protocol. Everything you will interact with as you write your code will be a finite logical system created by humans. You'll still have plenty of trouble getting it done, but at least you'll be able to tell yourself Look, this has to be possible.

But when you point a digital camera at the natural world, then start writing software to try understanding what it sees--you have now entered a whole new ballgame.

The difference is that the natural world is not a finite logical system.  You cannot write frozen logic to deal with input that has arbitrary variability. Of course you can try -- as I did for many years -- but what you will find is that you are forced to keep adding alternative pathways to your logic as ever more algorithm-breaking possibilities come to light (sorry) in your input until your code is so complex that every new feature breaks an old one and development grinds to a halt.

The architecture of normal computer programs--the set of techniques that underlay them all--consists of functions that generate results and that are connected to each other in a topology that is fixed at the time the program is written. For Machine Vision we will need something much more flexible.

The architecture we describe here will automatically adapt to significant changes in its inputs, and learn to improve its processing efficiency over time.

Abstractors

I will call the basic units of functionality in the Machine Vision architecture Abstractors. In normal programming, the fundamental units of logic are called functions, by analogy with mathematics. They are chunks of code that transform a set of inputs into a set of outputs. Abstractors have a more specific purpose: to creatively refine large quantities of data into smaller and more valuable representations--Abstractions. 

Most Abstractors can only function when an appropriate set of inputs become available--except for the lowest-level Abstractors in the vision system, which take a physical input (like light) and abstract it into images. These physical Abstractors are called Sensors. In special circumstances they may be controlled by higher-level Abstractors, but normally they simply operate on a timer. For example, creating a new image every forty milliseconds.

 

 

Abstractions are arbitrary Maps

In Go, it looks like this:

type Abstraction map[string]interface{}

A map using strings for keys and storing values that can be anything at all.

Abstractors that want to consume a particular type of Abstraction are written to understand its various fields and their datatypes.

The Bulletin Board

Unlike functions in a program, Abstractors are not connected to each other in a topology that is fixed when the code is written. Instead, Abstractors exchange Abstractions through a communications switchboard called the Bulletin Board.

When a new Abstractor starts running it registers with the Bulletin Board a function that will be used as a filter to determine what Abstractions will be of interest to it. Every time a new Abstraction is sent to the Bulletin Board, all such functions will be run. The new Abstraction will be sent to every Abstractor whose selector function returns a positive value.

Abstractors may register a new selector function with the Bulletin Board at any time, replacing the old one.

This breaks the fixed topology of standard programming. Abstractors that produce outputs do not know where they may end up. Abstractors that consume inputs do not know whence they come--only that they match the Abstractor's current criteria.

When an Abstractor starts up it also tells the Bulletin Board what type of Abstractions it is capable of creating.

Bottom-Up, and Top-Down

Initial activity in the system is bottom-up. It begins when one or more Sensors create images (or other sensory Abstractions) and send them to the Bulletin Board. These Abstractions will match the selection criteria of some Abstractors in the system, which will then receive them from the Bulletin Board and process them into higher-level Abstractions.

But as activity progresses, higher-level Abstractors may request specific work from lower-level Abstractors.

For example, imagine a system whose top-level task is to locate faint moving objects against a stellar background. It processes stacks of images and tries to locate the moving object in each image. The processing technique that it employs works if the asteroid is always reflecting approximately the same amount of light. 

But now it is trying to track an asteroid that is significantly elongated. As the object rotates, it sometimes presents its long axis to our system's sensor and the amount of light that it reflects is greatly reduced. Our tracker-Abstractor fails to find the object's location in several images of the stack. 

But Tracker wants to confirm the asteroid's position in those few images, or the quality of the Abstraction that it eventually posts will be significantly degraded. So Tracker calls for help.

To request assistance, Tracker issues a new kind of communication to the Bulletin Board: a description of work that he wants done -- what to look for, and where to look for it. The Bulletin Board matches this request with what it knows about what kind of work the other Abstractors around the system can do, and sends the request to all that look like they might be able to do the work. If any of those Abstractors decide to do the work, and if they succeed, the Tracker will incorporate their work into its Abstraction which will then be posted.

The work that Tracker initiated with its request is an example of top-down activity in the system.  Such requests may come all the way from the very topmost Abstractors whose Abstractions constitute the purpose of the system, and reach all the way to the bottommost Sensors.

The combination of data-driven bottom-up and goal-driven top-down action makes for chaotic--but meaningful--patterns of activity.

Positive and Negative Belief

In a standard computer program, a function will either produce a result or an error message. If there is no error, then you can trust the result. You can have that kind of perfect certainty when you're working with human logic: an HTTP server, a Kubernetes cluster, a file was opened or it wasn't.

When our code is pointed at the natural world, we can't have much of that kind of certainty. At the lowest levels we can -- when you are doing image processing operations -- an image goes in and a different kind of image comes out -- then, yes, you can be as certain of your result as any common program's function.

But as we approach the higher levels of actual vision -- in which the outer world is being meaningfully modeled -- abstracted into representations useful for further cognition -- from that point upward we can never again have perfect certainty.

Rather than just answers or error codes, Abstractions come with belief values attached. A belief can be positive or negative (disbelief), and a given Abstraction always has attached to it a value for both. Belief spans the range from 0 to 1, disbelief from 0 to -1. If a given Abstraction is merely uncertain, you will see a low belief number. But if there is actual contradictory evidence, you will see a nonzero disbelief number alongside the positive.

These values may be influenced by Abstractors other than the one that posted the original Abstraction. I.e., another Abstractor may come along and add some disbelief to a given Abstraction, because it is considering a kind of evidence that the original Abstractor did not -- and in that new view, something does not look right.

The Market

Higher-level Abstractors can request any amount of extra activity they want. If a given Abstractor becomes overloaded with work, I think there will at some point be a mechanism that allows more copies of it to be instantiated to share the load. With different experience, different settings, and different relationships, I think those new copies can have a distinct life of their own.

There may even be a way, someday, to create new Abstractors doing new types of processing, entirely from scratch, without human programmer intervention.

In short, we have a system here that can expand to fill up any amount of computational resources you care to provide. 

And that's a problem. We have finite resources, but a perceptual system that can expand without limit. And those resources are needed for other things besides visual perception! There is still higher-level cognition that the perceptual system is supposed to be supporting! That's the part that decides what the system should be doing, based on what it is seeing. It needs to have some compute power too.

We need a vision system that can somehow keep itself within some bounds of resource use, and yet handle new perceptual issues as they arise. We need a system that can quickly expand to use new resources if that is what is necessary to keep us alive, but which can then quickly 'learn' to solve that new perceptual issue more efficiently, freeing up computational power for other equally vital realms of cognition.

We need a system where overall efficiencies can arise as an emergent property of the interaction of many independent Abstractors.

We need a market.

The Abstractor Economy

And here I come to the end of what I know so far about this system. Everything up to this point I believe I know how to implement, but not this, not quite.

What provides the overall total resources that the system can use? Are those resources apportioned from the top down? But then how do the Sensors fire? Are they separate?

Is there a 'mainstream' of processing that happens without negotiation? Does the marketplace only affect top-down transaction in which a higher-level Abstractor requests specific work? But then how is that Abstractor compensated for the Abstraction that it posts.

Do Abstractors get compensated when one at a higher level uses its work? Do lower-level Abstractors 'bid' on work? Or do they do the work 'on consignment', hoping to be paid? Or both, at their discretion?

Do Abstractors have 'savings'? If they amass enough savings, is that what controls when they can reproduce?

If an Abstractor is 'thinking' about cost/benefit issues in this way, that implies a substantial amount of logic that is completely independent of its core processing logic -- the stuff it gets paid for. How is that logic implemented? And do different Abstractors have different 'styles' for this type of logic? Some being bigger risk-takers, hoping for greater rewards?

What happens when an Abstractor 'goes broke'? Can it ever function again?

Can it go on the dole and try to build up from there?

I can show one example of a system like this in action, based on our earlier example of an Abstractor trying to find a sequence of asteroid locations across a stack of images.

 

When Tracker discovers that it cannot detect the asteroid location in several of its images, it creates a work-request which it transmits to the Bulletin Board. That request specifies the type of work wanted, which is region-finding. The region found will be the asteroid in that image. It tells the prospective contractor a small bounding box in which it should look -- interpolating from the other images where it was able to locate the asteroid -- and it says about how big it should be.

Only one contractor manages to find the asteroid, and it is an exotic and expensive one. The problem is that the asteroid is reflecting so little light that normal grayvalue techniques cannot detect it. But this contractor succeeds by doing statistical analysis of the background noise. It discovers a region of just the right size in the right spot. The average grayvalue of that region is no greater than that of the background, but the standard deviation of its grayvalue distribution is three times greater than that of the typical background.

Tracker accepts its work, and pays the contractor. They form an alliance that lasts for hundreds of frames.

Eventually, however, another Abstractor and potential contractor notices the high prices that Tracker is paying for region detection in the problem images. This guy thinks "I can do that cheaper!" He could not bid on the initial solicitation because his technique did not work. But since then he has tried his technique again with many modifications -- spending his own savings to do so. He has discovered a set of modifications that allow it to work on the problem images, much more cheaply than the prices Tracker is paying.

Based on that research, the new contractor makes a bid on the work-request that Tracker submitted hundreds of frames ago. Seeing the lower-cost bid, Tracker tries out the new guy, and finds that it works well. Tracker switches contractors.

This kind of activity is going on all over the system. The net effect is to gradually reduce the overall resource consumption of the system, while maintaining effectiveness.

Next Steps

In the above description, I have one tiny little snippet of code. The next steps will be to make a lot more of those snippets, and finally to see how much of the behavior described above can be shown in a running system.

The ultimate goal is to show system-wide 'intelligent' behavior emerging from the chaotic interactions of these many independent Abstractors.

But, for now, leaving the Market behavior out of it. That still needs a lot of designing.

 

 

Vision for Asteroids

The best place in the solar system for our near-term future -- the next thousand years or so -- is the big strip between Mars and Jupiter where the asteroids live. It's a long way out there -- the near edge 18 light-minutes out from the Sun, and the far edge 27. For comparison, the Earth is only 8.3 light-minutes out.

And it's mighty thin out there. The Belt has a volume of something like 6000 cubic light-minutes, while the total mass of all the asteroids is about one two-thousandth that of the Earth. I think that probably means that you could fly through that belt one hundred times staring out your front window the whole time and never see a darned thing.

Which brings up the first vision task for the asteroids: finding one.

Our spacecraft will probably know where it's supposed to be going, but it would be just immensely better if it could locate its target visually while it's still distant, and correct it's own course without waiting for the hour round-trip message to Houston. Or maybe it won't know! Maybe we will want it to go prospecting for a rock that no one has ever seen before.

In either case, we will want to be able to detect our asteroid when it still looks like this:

Big sky.

Possible bogey. Zoom 2x.

Maybe...

Zoom 2x.

I see motion. Look near center of image.

Zoom 2x.

Motion detected! Calculating orbit.

Tally-ho! We have a rock.

So this gives us task number 1.

1. Detect and track faint moving objects against a nearly-unchanging stellar background.

 

But of course the stellar background won't always be unmoving. The spacecraft will sometimes have to change attitude, which will make the stellar background change slightly from frame to frame.

Which gives us task number 2.

 

2. Track a gradually moving stellar background.

 

What does that mean? To track the stellar background means you find each star -- or at least each obvious star -- in one frame. Then you find them all again in the next frame, and then for each star in frame n you figure out which one it is in frame n+1. So, for each star, you end up building a little history that says 'Here it entered the field of view in frame n, and then here it is in frame n+1, and here it is again in frame n+2... and here it leaves the field of view in frame n+m.'

And all this talk of stars ... eternal stars. Unmoving...This reminds me of something.

Sometimes in machine vision applications, in cases where the object to be inspected can be manufactured or altered in such a way as to make visual inspection easier -- circuit boards, for example -- the manufacturer is kind enough to print fiducial marks on the object.

Fiducial marks on a circuit board.

Those are marks designed to be easily located by a vision system. In the case of circuit board assembly, they allow a pick-and-place machine to put all the little chips in all the right places. That isn't done by humans, you know. And those machines need to be able, at least a little bit, to see.

Such marks need to be easy to find, and unchanging.

Well, guess what else has such marks.

 

The Fiducial Marks of the Cosmos!

 

 

The Cosmos has its own set -- as long as you don't move very far. And we are not planning to move far. This is not Star Trek, where we zoom around so fast that you can watch the stars drift by out your stateroom window. (Just don't think about that too hard...) We are planning to only go zooming around within our own little 1500-cubic-light-hour solar system. In fact only out to the asteroid belt -- more like half a cubic light hour.

From Manchester, Michigan, in the United States, North America, Earth in the year 2020 -- the great ring of the asteroids looks like the vastness of infinite space. 

To the Cosmos, it looks like nothing at all.

For all of our machines flying around the entire asteroid belt for the next thousand years while we build Solar Civilization, the Cosmos provides us with an ideal set of fiducial marks. They're easy to see, and they never change. They're the same for everyone, everywhere.

It would be easy to memorize ten thousand or so of the brightest ones scattered all over the sky. Our machines will be created already knowing them. Using them, any machine anywhere within Solar Civilization can orient itself to an absolute coordinate system and know exactly where it's pointing.

If it can then also locate the Sun (not hard to do) and a few planets -- and if it has information about how the planets move -- then that machine can also know exactly where it is within the solar system -- a 3D location -- and exactly when it is! The eight planets move like the eight hands of a great clock, never to repeat itself, not in a trillion years. 

If you can see them all, you can use that great clock to determine the correct time down to the hour.

the Big Clock

So finally to use these lovely fiducial marks we will have one more vision task for the stellar background.

3. Given an image which is a subset of a known stellar map, locate the image on the map.

There will be much more later, but with these three visual capabilities we will be able to see our way to get where we're going.

Statement of Purpose

 

 

I have an old suitcase in my basement that is full of scrapbooks that I made over the course of several years starting when I was eight years old. They are all full of newspaper articles about the US space program, the first article being a Sunday color supplement about the Gemini 11 mission.

 

Going Places

 

The suitcase also contains a newspaper article about me. The local paper sent a reporter to my school when I, at the age of eleven, wrote a letter to the federal government asking whether it might be possible for me to purchase a small piece
of the Moon.

I received a response from the State Department explaining that, while I was certainly free to visit the Moon, an international treaty prohibited anyone from claiming any of it. The photographer's picture shows me reading the response, looking mildly irritated.

In spite of such bureaucratic intransigence I was confident, in the summer of 1969, that it would prove to be no more than a minor speed bump on the road to the future.

 

 

It was only three years later, on 13 December, 1972, that Gene Cernan stepped off the surface of the Moon to climb the ladder into the Apollo 17 Lunar Module, and Project Apollo was terminated. I quit clipping out newspaper articles after that, because there weren't any more stories worth saving. It has now been forty-eight years since the last human being left the Moon.

 

I wanted to stay a while.

As I entered high school I began to understand that my future would not be full of rockets. But in my freshman year I read a book by Gerard K O'Neill called The High Frontier: Human Colonies in Space, and I started dreaming of building islands in the sky using nothing but sunlight and asteroids.

 

Islands in the Sky

Eventually I found my way to grad school where I fell in love with the highest-tech field I had ever heard of: Artificial Intelligence and Machine Vision. Hope in American space efforts was fading, weighed down by the miserable performance of the Space Shuttle. 

At the dawn of the decade we had been told that the Shuttle would fly five hundred missions in the Eighties, would reduce launch costs to a fraction of what they had been, would usher in a new era. But by January 1986, we'd had only 24 flights. Less than a tenth of what had been hoped.

 

I was on a lunch break from my first high-tech job, at a startup called Machine Vision International in Ann Arbor, sitting in my car in the drive-up line at the local McDonald's, when I heard on the radio that Challenger had died. When I pulled forward to accept my little bag of lunch from the McDonald's woman at the window, I was weeping.

When I got back to work some of my colleagues in the Research Department were standing outside and they asked if I had heard the news. Yes, I said, and now it's over. We just lost the US space program. Nancy said, "Oh, no, don't worry. They'll fix it and have it flying again in a couple months." "No," I told her. "More like two years."

I was close, if a little optimistic. It took two years and eight months before the shuttle flew again. By the end of the Eighties we'd had a grand total of thirty-two flights.

The Day the Future Died

Life went on: marriage, jobs, moving to California just in time to for a Michigan boy and girl to see what a real earthquake feels like, fleeing back to Michigan, bringing a new baby girl into the world.

The Nineties passed, and then the Oh-Oh Decade. 9/11 came. 

Then it was winter again, in early 2003, and I was in my car again -- this time getting the oil changed -- when Columbia broke up during reentry, raining its ruin upon east Texas.

Columbia, falling.

More years, more jobs. The Global Financial Crisis A good job at Red Hat! Our daughter going to college, and then finding her way to grad school. My wife rejoining the workforce. The Grandparents dying.

Until one day in early 2018 -- it was winter again -- I saw on the internet the most amazing video. I saw two rockets, made by a private company, after having delivered their payloads and reentering the atmosphere --- decelerating to a landing on their tails.

Just like they did in the science fiction movies when I was eight.

Over the next year, I think I watched that clip a hundred times.

 

They're here.

They're using vision systems to help land those rockets, I thought. Yes, OK, but too many years have gone by. Everything just took too long. Too much water over the dam. Good luck, younger people, and may all your rockets fly true.

Until the foul year of 2020 dawned, with viruses and riots and the biggest economic convulsion since the Fall of Rome. And the month of June came along and I was poking around the internet, daydreaming of rockets, when I came upon an interesting article.

Space is back, baby, she said. It’s back in the news, back in our thoughts, and back in the culture.

I read with interest.

The key is private industry: What used to cost the government $54,500 per kilogram of payload lifted to orbit now costs SpaceX $2,720, saving 95 percent.

That really got my attention. A factor of twenty reduction in cost.  I had just a short time before learned about the Erie Canal that opened almost two hundred years ago. It reduced the cost of westward travel by a factor of twenty-five or thirty -- and that's what opened my home state of Michigan to settlement. Back when it was the West.

If that has already happened because of SpaceX, I thought, then the road has opened. 

 

Fifteen years on the Erie Canal

 

She even mentioned the Outer Space Treaty, my source of long-ago irritation, and said that recent legal thinking is that just because states cannot lay claim to heavenly bodies like the Moon or Mars doesn't mean that private individuals can't have property rights over things like asteroids -- and the materials they might take from them.

See? the eleven-year-old said. I told you.

And then the author said:

Space law used to be entirely academic, but now it’s a rising field. NASA is funding asteroid-mining research. The Colorado School of Mines now has an asteroid-mining program of study.

When I read that last sentence it was like hearing a great bell toll. I'm going there, I thought, age be damned.

If I drop dead halfway through the program, that's fine with me. Well, you know. Fine-ish. What is not OK is not trying. I don't think eleven-year-old Mike would be happy with that, no, not one bit. So we're going.

They even have the same block-M as Michigan. I can re-use all my old school stuff.

I finished my application two days ago.

 

Go West, old man.

This is why we're doing this blog, and why we're processing images of stars. And why later we'll be trying to track things like the Lunar Landers moving against a background of stars, features on an asteroid's surface, structures taking shape in free space.

When we send machines out there to start exploring and mining and building for us, they might end up half a light-hour away from the nearest human being -- much too far to phone home for instructions for your every move.

Our machines will need to be able to see.

It's time to be making vision systems for the asteroids.

 

Tutti Frutti Sky

 OK, so I have made my first color image, and RGB is Not For Me.

After combining the three filtered images, R, G, an B into a single 48-bit color image, and then mapping that down into a normal RGBA tiff image, I then exaggerated the colors so that I would be able to see clearly what things looked like.

Here's what the stars all look like:

Umm. Yikes.

Dude -- where's my universe?

Here's what happened.

RGB color filters are lovely things if you're making a labor-of-love image of a big, beautiful galaxy or nebula. Like this one by F. Vanderhoven, an iTelescope user who won NASA's Astronomy Picture of the Day award with this photograph:

 You see that? That's what color is for. That is IC-2944, the Gamma Centauri Nebula, and it is 75 arc-minutes across! That's more than 5500 of my pixels! F. Vanderhoven must have taken multiple fields of view to cover the whole thing, probably using dozens of separate exposures and adding them all together with image-stacking software to make this beautiful image. It looks great.

But what happens when you try to do color images of stars that are only a few pixels across? What happens is that the stars twinkle. As the air changes, the image of the star changes. At the end of a ten-minute exposure the portion of the star's image that is brighter or dimmer is a matter of random chance. Put three of those images together, filtered for red, green, and blue light -- and then exaggerate the color differences so you can see them -- and you get the bizarre patchwork of colors that you see in my star image, above.

With some region-growing and averaging, it might be possible to set all pixels of each star's image to its average color, but that would be faking it and no doubt that effort would have its own problems. And -- unless you need the color data to be able to make a beautiful image like the one above -- the results will sure not be worth giving up two-thirds of your light to get.

So, I'm back to plain luminance for my images. I will still take three ten-minute exposures in my telescope sessions, but I won't interpose the color filters. I want every photon I can get. I will combine the images only by summing them to make a single brighter luminance image.

And I will say goodbye to the Tutti Frutti Sky.

Bright and Dark

 

Now let's look at objects, both bright and faint. Let's put little lines across them that sample and print out the pixel values, and see what they look like.

Here's one from the brightest star in the image: its profile in a graph, along with an actual slice of the image along the area that was sampled. And I have scaled up the tiny image slice to correspond pixel-for-pixel with what you see in the graph.

 

 What's interesting about this profile is that it does not rise to a point, but instead is mesa-shaped. That flat area at the top is probably what we should consider to be the 'real' object, while the rapidly falling off light of the steeply sloping sides is side-glow.

But don't imagine that the flat area -- 5 pixels across -- is the actual image of the star, though! We are nowhere near that kind of resolving power. A single one of telescope T11's pixels is 0.81 arc-seconds across. Even if we were looking at the very closest star -- 4 light-years away -- just one of T11's pixels would cover a distance of 22 million miles at that range. That is a span 26 times bigger than our own sun. So the 5-pixel flat area of this light profile covers a space 130 times wider than the Sun, even at the range of the closest star in the sky. Which is not what we are looking at.

So what we are seeing here is a tiny intense point of light, far away in space, spreading out as it passes through the Earth's atmosphere and moving around randomly because of motions of the air during what was a 10-minute exposure.

Still, the fact that some of that profile is so nice and flat rather than looking like a normal curve suggests that there are two different processes involved in illuminating the central 5 pixels and the 5 or 6 on either side of it. If I had to pick a specific boundary for this object in my image, I would pick that flat area from 325 to 330 on this image's X-axis.

Is that what all bright objects look like? Let's do another one. Here is a sample line across the bright star near the center of this image.

Yes, it looks similar. In fact, at 4 pixels diameter it's almost the same size. Just a little smaller, probably because this object is a little dimmer. It fills the central pixels to 47,000 gray values or so, while the first one filled them to 55,000. The central flat area is 4 pixels across here rather than 5, and the sides -- where light falls off to one-tenth of the central illumination in the space of 3 pixels, are also a little smaller. The brighter object takes 4 pixels on both sides to fall off the one-tenth of the center.

SO! We have a way to determine the edge of bright objects. If you look at these two curves, the point where the sloping wall meets the top of the mesa is a place where the slope of that line changes very quickly. That would be easy to find programatically. 

Now how about doing the same sample-line trick to a couple of extremely faint objects? 

The brightest pixels in this sample line are almost 200 times fainter than in the brightest star, but we can still discern something like the same mesa pattern. Except that this 'mesa' has a flat top only 2 pixels across, and it slopes down on either side less symetrically -- taking only a single pixel on the left side to reach the background, and several pixels on the right.

Can we find an object this faint, when its height above background is only a couple times higher than the average background fluctuations?

The second bright star is close enough to this faint star in the image that we can see both in a single view. Take a look:

The faint star isn't much, but I bet you can see it with no problem -- and with little doubt that it is not just a random background fluctuation.

Why is that?

I think I know -- but another faint object will illustrate the idea better. Let's look at a galaxy!

 

 

That is what you call a galaxy far, far away. (And long ago!) It's very faint, but you can clearly see it, right? Looking at the profile we see that, again, the height of the galaxy brightness profile is no better than double the average brightness fluctuations of the dark background.

If you were to try doing a normal grayscale threshold automatically, I think you would have a very hard time separating this kind of object from the background. But I think, with the help of a little bit of statistics, it might become a lot easier. 

But that ... is Another Story.

First Light

 Let's start by learning a little about our images. The first thing I'd like to know is -- how dark are the dark areas between the stars?  A gray16 image has 65536 possible gray values in it, and it's quite possible that the areas that look like black background could be hundreds of gray values above zero.  Also, how uniform are the dark areas? That will have a lot to say about our ability to find faint objects later.

So, first thing to do is take a histogram and see what we see.

Using the  Histogram_gray16() function from my v6 library, and a little gnuplot, we see this:

Which is perhaps not very helpful.

It does look as expected: a huge spike of pixel-count far to the left, because a picture of the night sky is always going to be mostly very dark pixels, and a nice even smattering of brighter pixels all across the rest of the range, because the myriad stars come in all brightnesses.

But let's zoom in on the dark pixels -- see what it will take to separate foreground from background reliably. See if we can do that while still finding very faint objects.

Tell gnuplot to only plot ... let's say the bottom 500 gray values, and we get this:

And that is a beautiful normal curve.

It's not all the way down at zero, because the dark sky is never perfectly dark, and this sensor is quite sensitive enough to pick up any kind of skyglow. 

Make a new tool in v6 to just list out the pixel values as ASCII, modify it to only list values at 300 or below, run those numbers through a statistics program, and we see that the mean of that curve is at 182 and its standard deviation is 29.

So I wonder: what if we were to threshold this image only 2 sigma above the mean of that dark-pixel distribution. That should leave only about 1% of the background pixels. Will that be thin enough?

Threshold at 240...

 

That looks really good.

Oh, and thanks for the satellite, Elon. You better bring me some good internet with those things, because they're going to be pretty hard on my astronomy hobby.

 

Let's zoom in on the central star...

 

Yes, that's glorious.

The 1% or so of background pixels that we let through are randomly scattered all over -- so if you see a substantial clump of them -- like we do right near the bottom of this image -- that has real good odds of being an actual object -- just very faint. And one which we would have lost if we had thresholded at 2.5 or 3 sigma.

 

We will never actually binarize the image, oh no, that would throw away practically all the lovely data. But this looks like a good way of deciding which pixels we can safely ignore.