A Killer App on a non-Consumer MC68000-based Platform

[bill75]

In 1986 Cognex developed an industrial machine vision killer app—software so valuable that customers bought the platform on which it ran in order to run the app. The platform was the Motorola 68000-based Cognex 2000, and the software was called Search.

At the time we did not understand that we had a killer app (the term itself would not be coined for another two years)—we were just trying to solve one specific problem for one customer. But it didn’t take long for us, and for the market, to realize what we had. Three years later we had our initial public offering on Nasdaq.

At the heart of the Cognex 2000 was a novel image processor that we called VM7, tightly coupled to the 68000. VM7 was not a typical coprocessor that added instructions to the CPU, like for example a floating point coprocessor. Instead it augmented instructions that already existed, turning them into powerful image processing operations.

In 1986 the architectural details of VM7, and how it coupled to the 68000, were trade secrets. That ended in November 1990 with the issuance of US Patent 4,972,359, placing in the public domain the exact details of its operation. As a result I can describe in detail how it worked, and will do so in a series of posts beginning with this one. I drafted the patent myself, with advice from attorneys of course, but it’s an engineer’s description, not legalese. I took seriously my duty to enable “one of ordinary skill in the art” to practice the invention as well as I could.

The patent itself expired in 2007. The claimed method and apparatus are now public property. The technology is quite obsolete in 2026 for its original intended purpose, but it’s not inconceivable that someone might yet find some use for it.

VM7 was remarkably simple and inexpensive for what it was capable of doing when coupled with carefully arranged 68000 instructions. Perhaps most remarkable was its ability to compute grayscale normalized correlation (NC), the key enabling operation used by Search. Normalized correlation is a measure of the similarity between a pre-trained template and a like-sized portion of an image, with the property that linear changes in the image pixel values (i.e. gain and offset changes) have no effect on the result. Linear manufacturing variations, lighting and image formation changes, and other effects are simply ignored. The ability to compute NC with large templates (e.g. 128x128 pixels) on inexpensive hardware at high speed in 1986 was what made Search a killer app.

The standard formula for NC shows that for every template/image pixel pair, two multiplies and three adds are needed. At the time multiplies were very expensive. The 68000 with VM7 could do the same thing with zero multiplies and two adds per template/image pixel pair. And one of the adds was just an increment. This was not an approximation, it was the same exact result.

If you want to hear more, stay tuned.

The Cognex 2000

[bill75]

One of the key enabling technologies in semiconductor manufacturing is non-contact alignment. Wafers and the chips they contain have to be aligned to high precision with the electro-mechanical devices that operate on them.

Consider for example a processed wafer coming out of the fab for what’s known as back-end processing. The first step is to determine which of the individual chips are good and should be further processed, and which don’t work and should be discarded. A prober makes electrical contact with the bond pads on each chip in turn and runs electrical tests. Precise, microscopic alignment between the probes and the pads is required. To accomplish this a human operator looking at a screen chooses a portion of an example wafer to use as a template. In operation a machine vision system locates the template in images of a test wafer at two points, so that position and orientation can be calculated.

After probing the wafer is cut into individual chips by a saw. The chips that passed electrical test are robotically inserted into a package. A bonder attaches thin wires between the pads and the package leads to bring the signals to the external world. Each of these steps is done on different, specialized machines, and each requires precise, microscopic alignment. The economics of semiconductor manufacturing require that alignment systems be fast, inexpensive, and highly reliable. The general rule in engineering is that among fast, cheap, and good you get to pick any two, but not all three at the same time. Not so for alignment.

Up until the introduction of Patmax at Semicon West in 1997, alignment was a template matching affair. With the severe limitations of microprocessors and TTL logic in the 1980s, before Search alignment was strictly binary template matching. The human operator, in addition to selecting the portion of the example image to use as a template, had to choose a threshold to binarize the source grayscale image, turning every pixel into a one-bit, yes/no value. Similarity was measured simply by counting the number of template bits that match corresponding image bits. Thresholds were the weak point in the process—operators struggled to choose them, and ordinary manufacturing variations would degrade reliability.

From its founding in 1981 until the development of Search, Cognex was strictly an industrial OCR company. We sold PDP-11-based equipment that could read, for example, characters laser-engraved on wafers, jet engine turban blades, and nuclear fuel rods. A Silicon Valley customer used our OCR system to read wafer serial numbers, and a competitor’s binary template-matching system for alignment. But the customer grew tired of paying for two separate systems from two separate vendors, as well as using two proprietary, incompatible APIs. So they issued a challenge—whichever company could offer a system that did both OCR and alignment would win all the business.

There was a fierce debate at Cognex over whether we should accept the challenge, which would require devoting scarce resources to an effort that would likely prove fruitless. We had no alignment technology, and the competitor had an inherent advantage—OCR was important, but alignment was indispensable. The customer would rather bet on virgin OCR than virgin alignment.

Those advocating to accept the challenge prevailed, and it fell to me to develop an alignment product. It had to be as good as the competitor’s system, but it did not have to be better as long as we maintained the OCR edge.

Binary template matching would be fine, but I was never going to do that. The competitor had patents that I needed to steer clear of, and we had no binary image processing infrastructure to build on—our OCR technology was grayscale from the ground up. On an emotional level, I detest binary thresholds and avoid them wherever possible, which is almost always and everywhere. Thresholds discard information, and vision is hard enough without immediately starting with much less information than is available.

In 1986 the Cognex 2000 was under development as a platform to replace the PDP-11 with the 68000 for our OCR technology. VM7 was part of the design. It became clear that it could do much more than OCR—it could maybe possibly support large template grayscale normalized correlation at microprocessor cost and economically useful speed, what everyone knew was impossible.

[bill75]

The Motorola 68000 was a masterpiece. It was a 16-bit microprocessor as measured by bus width, but a 32-bit machine as seen by the programmer, with a flat address space and 16 32-bit registers. Migration to the soon-to-arrive true 32-bit cousins (e.g. 68020) was trivial, unlike the x86 nightmare.

The key to the 68000’s brilliance was that it copied almost all of the groundbreaking features of the PDP-11, and fixed its few but serious flaws. The 11 had not quite enough registers and a 16-bit virtual address space, woefully inadequate for the DRAM era.

The virtual address space limit was ultimately fatal for the 11. Sure you could expand physical memory through memory-mapped segmentation, but using that memory required software mechanism that was susceptible to bugs that simply can’t exist in a flat address space. And it gets much worse when a team is writing the code, with modules written by different authors having different expectations for what segments are currently accessible.

Cognex engineering suffered with this for years but finally it was too much. The 68000 was easy to fall in love with.

Our 68000 ran at 12.5 MHz, with 4-cycle no-wait-state DRAM memory, 320 ns/memory cycle. We used 22 of its 24 address bits to access a 4 MB address space: 2 MB DRAM, EEPROM, 300 KB frame grabber video memory, PDP-11-style I/O space, and 1536 bytes of SRAM in VM7.

The other two address bits are where things start to get interesting. They were invisible to and ignored by the memory system. They were instead opcodes for VM7—they told it what to do with the bytes read or written by a memory transaction. They didn’t change what the CPU sees, they augmented whatever the CPU was also doing.

[bill75]

In 2026 it can be difficult to remember just what 1986 was like. With a 12.5 MHz clock and four clocks per 16-bit memory transaction, the bandwidth works out to 50 megabits per second, half the speed of my slowish internet connection at home. Think about that. Imagine if a CPU had to go out on the net to fetch each machine instruction, one at a time! A register to register add took 320 nanoseconds, about 30,000 times slower than my quad-core AVX2 laptop. Integer multiply needed 5600 nanoseconds. Meaningful comparison is difficult, but call it a half-million times slower. Floating point was a software function call, and you can imagine how slow it must have been. My seven-year-old laptop can do eight single-precision floating point multiplies per clock per core.

[bill75]

Here is a block diagram of VM7:

There are three 256-element arrays implemented in SRAM:

• 8-bit wide translation array T
• 16-bit wide energy array E
• 24-bit wide correlation array C

Each array appears in the address space of the 68000, and elements can be read and written like ordinary memory. The Array Control block handles these transactions. Generally the arrays are initialized at the start of an image processing operation and read out at the end for post-processing to get the final results.

The FIFO Control watches transactions on the CPU bus and decodes the high two address bits, which are invisible to and ignored by the memory system. Every bus transaction contains one or two bytes to be read from or written to 68000 memory. The CPU breaks 32-bit longword operations into two 16-bit words.

The I FIFO is a 4-element, 8-bit wide first-in first-out buffer that receives image bytes from FIFO Control, extracted from CPU bus transactions as described below. The M FIFO is an 8-element, 9-bit wide buffer that can be operated as a FIFO or a ring buffer. It receives model bytes from FIFO control, with the 9th bit used to specify addition or subtraction.

Address bits 23:22	Operation
00	Do nothing.
01	Insert image bytes into the I FIFO. If the FIFO is full, insert memory system wait states until there is room.
10	Insert model bytes into the M FIFO at the location addressed by the Write pointer. The ninth FIFO bit is cleared to mark the bytes for addition. Advance the pointer modulo 8.
11	Insert model bytes into the M FIFO at the location addressed by the Write pointer. The ninth FIFO bit is set to mark the bytes for subtraction. Advance the pointer modulo 8.

Whenever the I FIFO is not empty, the following happens:

• An image byte I is extracted from the I FIFO.
• The image byte is mapped by the T array to produce I’.
• The energy array (E) element addressed by I’ is incremented.
• A model byte M, and add/subtract bit B, are read from the M FIFO at the location addressed by the Read pointer. Read is advanced modulo 8.
• I’ is added to or subtracted from the correlation array (C) element addressed by M.

One might write this in C:

iPrime = T[i];
++E[iPrime];
if (B == 0)
  C[M] += iPrime;
else
  C[M] -= iPrime;

Given the size of the E and C arrays, up to 65,536 image/model pairs can be processed with guaranteed no overflow. In practice many more can be processed without overflow.

The E adder and the C adder/subtractor are implemented as byte serial operations. The low byte is added or subtracted, and higher order bytes are processed only if there is a carry/borrow out of a lower order byte. E adder carries are obviously rare. C carries to the middle byte are more frequent, and to the high byte are rare.

The processing of every image/model pair uses three CPU clocks, plus one for each byte-serial carry. The maximum processing bandwidth depends on how the software organizes the memory transactions, further described in subsequent posts. With proper coding techniques we can process image/model pairs at close to 80% of the theoretical maximum bandwidth of the memory system. The VM7 bus monitoring system achieves much higher bandwidth than I/O device-style reads and writes could, and very close to the maximum that a much more complex DMA controller could do. Considering that VM7 adds only about 20% more hardware to the bare minimum that any machine vision system must have, cost/performance is remarkable.

That’s it. That’s everything VM7 does. Everything else is up to software running on the CPU.

Next we’ll take a closer look at normalized correlation (NC). Its key properties and the conventional computation with two multiplies and three adds per image/model pair (here I use template and model interchangeably). Then with some middle school math we’ll replace the per-image/model multiplies with per-gray level multiplies. A large template might have 16,384 model values but only 256 gray levels. Next, with some retro-math we’ll replace the per-gray level multiplies with adds. Not a single multiply remains.

Getting the math right is necessary but not sufficient. We’ll see that the maximum theoretical rate at which image/model pairs can be processed by the 68000/VM7 combo is 80% of the maximum memory bandwidth. To achieve in practice very close to 80% we use a model compiler, a routine that generates at runtime optimum machine language code to process the data.

[jayemm]

Thanks for writing this and sharing it with us. Fascinating story.

Re: rememberin what it was like in 1986, I do remember pretty well: I was at 5 years from the start ofy career, on my 3rd job, and doing systems programming (in C on QNX) with crappy 8088 PC clones (and feeling pretty good about that since I’ve just upgraded from even crappier Z80 machines running assembly on CP/M and similar). Read a lot about the 68000 and salivated about it, but having access to one was still 8-9 years in the future for me.

Good memories overall.

Just a small typo alert: “jet engine turban blades”, I’m pretty sure you meant “turbine”

[bill75]

Oops, should be turbine. That’s embarrassing. Good catch, I appreciate the close reading.

[bill75]

Reposting now that MathJax is enabled.

A template matching system used for alignment generally operates as follows:

Training

• An example object is presented to a camera, which captures an image.
• A portion of the image is chosen to serve as a template. The template pixels are optionally processed in some way, and stored in memory.
• The location of the template in image coordinates is stored in memory.

Runtime

• A test object is presented to the camera, which captures an image.
• The system finds the location in the image that is most similar to the template, according to some definition of similarity.
• The found location relative to the trained template location is converted from image coordinates to world coordinates to indicate the position of the test object relative to the trained example object.
• The similarity score at the found location indicates relative confidence that the template has actually been found and the location should be trusted.

Normalized correlation (NC) is an ideal measure of similarity for a template matching system due to its mathematical properties, which we’ll now explore (note that template matching for alignment has been obsolete since the late 1990’s).

One common definition of NC is

r = \frac{\sum (I_i - \bar{I})(M_i - \bar{M})} {\sqrt{\sum (I_i - \bar{I})^2} \sqrt{\sum (M_i - \bar{M})^2}}

Here I_i is the i^{th} image pixel, and M_i is the corresponding model (template) pixel. \bar{I} and \bar{M} are the mean image value and mean model value, respectively. The sums are over all i.

NC has properties that make it a great similarity measure:

1. Adding a constant to every image or model pixel does not change r.
2. Multiplying every image or model pixel by a constant does not change r.
3. If I_i = a M_i + b for all i then r = \pm 1 (same sign as a).
4. Otherwise, |r| \lt 1.

#1 and #2 make NC independent of image contrast and brightness, so that ordinary manufacturing and lighting variation, for example, don’t degrade reliability. Operators can’t choose a bad threshold because there is none.

Properties 1-3 are easy to prove with a little algrbraic manipulation. Start by proving #1, noting that

\bar{I} = \frac{1}{N} \sum I_i

Then you can without loss of generality set \bar{I} = 0 and \bar{M} = 0. Then it’s simple to prove #2, remembering that \sqrt{a^2} = |a|. Once #1 and #2 are established, it’s sufficient to prove #3 for the special case I_i = M_i. #4 is harder to prove but it’s true.

Properties 3 and 4 establish what NC considers to be a perfect match. That |r| \le 1 makes r a great measure of confidence because it has an absolute meaning independent of whatever units the graylevels measure.

The above formula for NC is great for understanding its properties but not for computation. As written it takes two passes over the data, one to compute the means followed by one to compute the sums. NC can be rewritten for one pass:

r = \frac{N \sum I_i M_i - \sum I_i \sum M_i} {\sqrt{\left[N \sum I_i^2 - \left(\sum I_i \right)^2 \right] \left[N \sum M_i^2 - \left(\sum M_i \right)^2 \right]}}

So we need these sums:

\sum I_i M_i \quad \sum I_i^2 \quad \sum M_i^2 \quad \sum I_i \quad \sum M_i

The sums that depend only on model pixels can be precomputed. The three remaining sums that depend on the image require two multiplies and three adds per image/model pair. Next we’ll see how to get to the promised zero multiplies and two adds. You can see the two adds (one just an increment) in the VM7 diagram, but where did the multiplies go?

[bill75]

Let’s look at a simple example of computing \sum I_i M_i with some made-up values:

\sum I_i M_i = 1 \cdot 4 + 1 \cdot 5 + 2 \cdot 7 + 3 \cdot 7 + 4 \cdot 9 + 3 \cdot 8 + 2 \cdot 6 + 2 \cdot 5 + 2 \cdot 5 + 1 \cdot 3 = 139

We have 10 image/model pairs, 10 multiplies and 10 adds. Although there are actually only 9 adds above, and some of the multiplies are by 1, code would not know that and do them all.

With a little middle-school math let’s factor the sum of products:

\sum I_i M_i = 1 \cdot (4 + 5 + 3) + 2 \cdot (7 + 6 + 5 + 5) + 3 \cdot (7 + 8) + 4 \cdot (9) = 139

The factorization gives us 4 multiplies, one for each model graylevel, plus the 10 adds. With templates much larger than the number of graylevels, this is a big win. We’ll get rid of those multiplies later, but for now notice that this factorization is precisely what would be in the VM7 correlation array C after processing those image/model pairs. We can write the C array post-processing like this:

int sumIM = 0;
for (int i = 1; i < 256; ++i)
  sumIM += i * C[i];

Similar analysis applies to \sum I_i and \sum I_i^2, with this post-processing of the energy array E:

int sumI = 0, sumI2 = 0;
for (int i = 1; i < 256; ++i)
{
  int iE = i * E[i];
  sumI += iE;
  sumI2 += i * iE
}

Notice the following:

\sum I_i M_i = \sum i \text{C}[i] \quad \sum I_i = \sum i \text{E}[i] \quad \sum I_i^2 = \sum i^2 \text{E}[i]

In general, \sum i^k X[i] is the k^{th} moment of X, and so we need the first moment of E and C, and the second moment of E. In the next post we’ll see that any discrete moment can be generated entirely without multiplies.

[bill75]

In the previous post we saw that we can compute the sums needed for NC with a two-step computation: factorization followed by moment generation. VM7 does the factorization with its two adds per image/model pixel pair. The 68000 will do the moment generation, which we wrote like this:

\sum I_i M_i = \sum i \text{C}[i]

int sumIM = 0;
for (int i = 1; i < 256; ++i)
  sumIM += i * C[i];

\sum I_i = \sum i \text{E}[i] \quad \sum I_i^2 = \sum i^2 \text{E}[i]

int sumI = 0, sumI2 = 0;
for (int i = 1; i < 256; ++i)
{
  int iE = i * E[i];
  sumI += iE;
  sumI2 += i * iE
}

This requires three multiplies and three adds per graylevel (I’m ignoring loop control overhead—it’s easy to unroll loops that have compile-time iteration limits). But there’s a much better way to do moment generation, using a technique called cascaded accumulators:

int d0 = 0, d1 = 0;
for (int i = 255; i > 0; --i)
{
  d0 += C[i];
  d1 += d0;
}
int sumIM = d1;

int d0 = 0, d1 = 0, d2 = 0;
for (int i = 255; i > 0; --i)
{
  d0 += E[i];
  d1 += d0;
  d2 += d1;
}
int sumI = d1;
int sumI2 = 2 * d2 – d1;

Here we have five adds per graylevel and zero multiplies. Note that the accumulators d0, d1, d2 would just be 68000 data registers (which is why I named them with a d and not an a). The five statements inside the loops would each be a single 68000 instruction, for example

add.l (a0)+, d0     ; a0 -> E array
add.l d0, d1
add.l d1, d2

There’s nothing faster on any stored program machine than a register-to-register add, so these loops would fly. I’m sure I wrote the loops in assembler, because back then I didn’t trust C compilers to do the right thing.

Some obvious questions: Why does this work? Why loop backwards? Why the odd expression for sumI2?

I’m not going to derive all the math here, but perhaps I can provide some intuition about what’s going on.

When I was in high school learning calculus, I wondered what would happen if instead of taking the limit of various functions as \Delta x approaches zero, I just set \Delta x = 1. I worked out formulas for the \Delta x = 1 analog of derivatives and integrals of polynomials and other interesting functions. We can call these differences and sums, but I don’t remember what I called them. Here are some indefinite sums for polynomials that I wrote in my notebook:

You can see that the high-order term in each sum is the same as for integrals, and there are lots of lower-order terms that result from not taking the limit. And just like with integral calculus, the sums increase the order of the polynomial.

Years later I learned that all this is part of a branch of mathematics called the Calculus of Finite Differences. It’s not used as much today as it used to be, before mechanical calculation became available, but it does still have some applications. That’s why I called it retro-math in an earlier post.

Cascaded accumulators can be analyzed mathematically using these sums, and that’s how they manage to generate moments—each successive accumulator increases the order of a polynomial by 1, although the details are not straightforward. So for example with our three accumulators for the E loop, the final one is generating second-order polynomials, which is related to the second moment we want.

I say “related to” because, as you can see for the \sum I^2 case, in general moments are a linear combination of what ends up in the accumulators. Since it’s a linear combination, we can convert a column vector of accumulators to a column vector of moments with a matrix multiply. Here is what this looks like for five accumulators and the first five moments:

\begin{pmatrix}M_0 \\ M_1 \\ M_2 \\ M_3 \\ M_4\end{pmatrix} = \begin{pmatrix}1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & -1 & 2 & 0 & 0 \\ 0 & 1 & -6 & 6 & 0 \\ 0 & -1 & 14 & -36 & 24\end{pmatrix} \begin{pmatrix}A_0 \\ A_1 \\ A_2 \\ A_3 \\ A_4\end{pmatrix}

Finally, why loop backwards? Suppose we give accumulator 0 the simplest input: a 1 followed by zeros. In discrete signal processing theory this is called the unit sample. The output of the accumulators for this input is called the sample response of the system. One of the fundamental principals of the theory of these kinds of systems (linear shift-invariant), like F = ma in physics, is that the response of the system to any input is completely determined by the sample response, and is equal to the convolution of the input with the sample response. And for convolution, either the input or the sample response is flipped backwards. That’s why we loop backwards.

Well that’s enough math, right? Let’s see what the code looks like.

[bill75]

To really appreciate the speed advantage of cascaded accumulators for moment generation in 1986, let’s see what the inner loops would look like, and count clocks. Here is the straightforward loop with multiplies, assuming it’s unrolled to avoid loop control overhead.

(One thing to keep in mind when looking at the code is that 68000 memory organization is big-endian—high-order bytes and words are at lower (even) addresses (but bit numbering was little-endian). This is one of the few things that Motorola did not copy from the PDP-11. I don’t want to debate big vs little endian in this thread, I’ll just say I have strong feelings about it.)

; d0  array index i
; d1  working register
; d2  sum IM
; d3  sum I
; d4  sum I^2
; d5  shift count
; a0  -> C array
; a1  -> E array                                 clocks
move.w (a0)+, d1      ; fetch C[i], high 8 bits      8
mulu d0, d1           ; i * C, high 16              40
lsl.l d5, d1          ; << 16                       40
add.l d1, d2          ; sumIM += i * C[i], high 16   8

move.w (a0)+, d1      ; fetch C element, low 16      8
mulu d0, d1           ; i * C, low 16               50
add.l d1, d2          ; sumIM += i * C[i],           8

move.w (a1)+, d1      ; fetch E[i]                   8
mulu d0, d1           ; i * E[i]                    50
add.l d1, d3          ; sumI += i * E[i]             8
mul d0, d1            ; i^2 * E[i]                  50
add.l d1, d4          ; sumI2 += i * i * E[i]        8

add.w #1, d0          ; update index                 8

Total 294 clocks. For the multiplies I estimated—the manual says max 70 clocks, I guessed what a shift-add algorithm might do. The lsl (logical shift left) instruction surprised me. First that I could find no other way to move or swap words in a longword register. Second that it costs two clocks per shift—no barrel shifters yet.

Now the cascaded accumulator version.

; d0  C accumulator 0
; d1  C accumulator 1
; d2  E accumulator 0
; d3  E accumulator 1
; d4  E accumulator 2
; d5  E[i], high word is 0
; a0  -> C array
; a1  -> E array             clocks
add.l –(a0), d0    ; C acc0     16     
add.l d0, d1       ; C acc1      8
move.w –(a1), d5   ; 0-extend E 10
add.l d5, d2       ; E acc0      8
add.l d2, d3       ; E acc1      8
add.l d3, d4       ; E acc2      8

Total 58 clocks, a little over five times faster.

Another thing to love about the 68000—you can just count clocks and know how fast the code will run. Here’s how I thought about loops back then. For cascaded accumulators I know I must fetch a longword from C, fetch a word from E, and do five longword adds. That’s what I call payload—code that does the required computation. The rest is scaffolding—code that supports payload. Here 50 of the 58 clocks are payload. The only scaffolding is 2 clocks for each pre-decrement, and 4 clocks to fetch the move.w instruction (whose purpose is to zero-extend the E value). 86% payload is excellent—I’m confident I can’t do any better on the 68000, so call it done.

Today we’ve got superscalar CPUs with deep, out-of-order pipelines, and multiple levels of cache. I love the performance but I’ve lost control of the clocks.

[bill75]

There’s a bug in the code I posted for the loop with multiplies that I need to correct. The final multiply is the array index i (8 bits) times the previously computed i * E[i] (24 bits) to get i * i * E[i] (32 bits). But the multiply instruction can only handle 16-bit operands. Also, there is a more efficient way to move a word around than the lsl.l instruction. Here is the corrected code:

; d0  array index i
; d1  working register
; d2  sum IM
; d3  sum I
; d4  sum I^2
; d5  i * i
; a0  -> C array
; a1  -> E array
; sp  -> longword with 0 in LSW                  clocks
move.w (a0)+, d1      ; fetch C[i], high 8 bits      8
mulu d0, d1           ; i * C, high 16              40
move.w d1, (sp)       ; create longword product      8
add.l (sp), d2        ; sumIM += i * C[i], high 16  14

move.w (a0)+, d1      ; fetch C element, low 16      8
mulu d0, d1           ; i * C, low 16               50
add.l d1, d2          ; sumIM += i * C[i], high 16   8

move.w (a1), d1       ; fetch E[i]                   8
mulu d0, d1           ; i * E[i]                    50
add.l d1, d3          ; sumI += i * E[i]             8

move.w (a1)+, d1      ; fetch E[i]                   8
mul d5, d1            ; i * i * E[i]                60
add.l d1, d4          ; sumI2 += i * i * E[i]        8

add.w d0, d5          ; update i and i * i           4
add.w #1, d0          ;                              8
add.w d0, d5          ;                              4

Total 286 clocks. Slightly faster than the previous loop due to replacing the lsl.l, but still about 5x slower than cascaded accumulators.

[bill75]

The 68000/VM7 system supported two basic modes of operation:

• 68000 touches image/model pairs (read or write) using image and model address codes, M FIFO acts like FIFO
• 68000 touches image pixels (read or write) using image address codes, M FIFO acts like a ring.

The maximum rate at which the memory system can put image/model pairs on the bus is one pair (two bytes) per memory cycle, which is four clocks per pair. VM7 can easily keep up with that rate, so the bottleneck in pair mode is how efficiently code can use the bus.

The maximum rate at which the memory system can put image-only pixels on the bus is two per memory cycle, two clocks per pixel. VM7 needs a little over three clocks. If code can use the bus efficiently enough, VM7 would be the bottleneck in image-only mode.

On the 68000, there is exactly one instruction that uses the bus most efficiently: compare memory long:

cmpm.l (aMdl)+, (aImg)+     ; pair mode
cmpm.l (aImg)+, (aImg)+     ; image-only mode

cmpm.l compares two longwords fetched from memory, post-increments the address pointers, and sets the condition codes (which we don’t care about). aMdl is any address register with the address bits 23:22 set to 10, likewise for aImg with the address bits set to 01. With pair mode the model bytes are fetched first.

cmpm.l takes five memory cycles to fetch four image/model pairs, or eight image-only pixels, with one extra cycle to fetch the instruction. With pair mode that’s a theoretical max of 4/5 = 80% of the max memory bandwidth. Theoretical because there’s gonna be overhead. 80% is a target, not a guarantee. But it’s nice to have a target, because then you know when you’re done.

In image-only mode the best we could do is VM7 speed, three clocks per image-only pixel. cmpm.l can do eight bytes per 20 clocks = 2.5 clocks/image-only pixel. If we could keep overhead low so that 2.5/3 = 83% of the execution time is cmpm.l instructions, that’s the best the hardware will support.

A good simplicity-speed tradeoff was to have a subroutine that can be called to touch an entire pair of image/model rows, or an entire image-only row, with no loop overhead. All the loop overhead is per row, not per pixel. The challenge was that we did not know at compile time the row size, nor the image row alignment at a given image location. We could, however, guarantee that each row in a given image has the same alignment, and that model rows are even-aligned. Alignment was important because the 68000 cannot do a word bus transaction at an odd address, and even if it could it would still be extra bus transactions.

In the description of VM7 I forget to note that the model value 255 is a don’t care—the image/model pair is ignored. We padded odd-width models with a don’t care at the end of each row so that model rows are of even size.

There are eight cases to consider for designing row loops for use with image/model pairs, corresponding to odd/even row alignment and row size modulo four. The simplest row loop can handle three of the cases.

; d0    image address update
; d1    row count
; a1    model address + M pixel code
; a2    image address + I pixel code
;
loop1:  cmpm.l (a1)+, (a2)+  ; 64 of these to handle row size <= 256 
        ... 
        cmpm.l (a1)+, (a2)+
        adda.l d0, a2
        dbf d1, loop1        ; offset adjusted at run time for row size

Alignment	Size % 4	Operation
even	0	Straightforward operation of the loop
even	3	Round up row size to multiple of 4 for dbf offset. The model has been padded with don’t care for the image pixel beyond the end.
odd	3	Round up row size to multiple of 4 for dbf offset, and decrement the starting row address to make it even. Preload a don’t care into the M FIFO so that the first pixel of the first row (even address) is ignored. At the end of the row, there is still one extra M in the FIFO, which is the padded don’t care from the model row, so the next row is ready to go.

If we replace the final cmpm.l in the above loop with cmpm.w, it can handle the cases of even alignment, size % 4 = 2, and even or add alignment, size % 4 = 1, using the same strategy as above. Only two cases remain.

Here is the loop for odd alignment, size % 4 = 0:

; d0    image address update
; d1    row count
; a1    model address + M pixel code
; a2    image address + I pixel code
; a3    address of a don’t care + M pixel code
;
loop1:  cmpm.l (a1)+, (a2)+  ; 64 of these to handle row size <= 256 
        ... 
        cmpm.l (a1)+, (a2)+
        tst.b (a2)+
        adda.l d0, a2
loop2:  tst.b (a3)
        dbf d1, loop1        ; offset adjusted at run time for row size

We decremented the starting row address to make it even and start at loop2 to preload a don’t care into the M FIFO. Since the first image pixel (even address) is ignored, the tst.b does one more at the end of the row, which consumes the extra M. There is no padded don’t care at the end of the model row, so another tst.b preloads one for the next row. The dbf offset was adjusted to reflect the row size and the various adjustments.

The final case is odd alignment, size % 4 = 2. This is identical to the above loop except that the final cmpm.l is replaced with a cmpm.w.

At run time we looked at the image alignment and row size, choose the right loop, adjusted the dbf offset, and in one case preloaded a don’t care M pixel. The vast majority of bus transactions used cmpm.l, so we got pretty close to 80% of max memory bandwidth. Similar strategies were used for image-only operation.

For NC, the 68000/VM7 system processed image/model pairs at a rate that was very close to five clocks per pair, 400 ns/pair, 2.5 million pairs/sec. A 128x128 model would need about 6.6 ms. The cascaded accumulator loop needed 24 clocks per model graylevel and 34 clocks per image graylevel. If both used all 256 graylevels, that’s 14,848 clocks. Call it 15,000 with some overhead, or 1.2 ms, for a total of about 8 ms with some overhead. Remember that this was at one position in the image—clearly strategies were needed to drastically reduce the number of positions that had to be evaluated, but that’s beyond the scope of this thread.

Time could be reduced by reducing the number of graylevels used. In practice, 64 image levels and 24 model levels were usually quite sufficient. The model levels could be reduced by various means, and since that’s done only at training time it doesn’t add to the runtime. The image levels could be reduced at no runtime cost using the T array to implement any desired mapping. These reductions could shave a millisecond off the total time.

While computing NC was the most commercially valuable operation for the 68000/VM7 system, it was quite flexible and could do many other operations that were important in the early years of industrial machine vision. Next we’ll look at a completely different operation that uses both image/model pair and image-only operation, as well as the T array and moment generation by cascaded accumulators.

[bill75]

A very popular industrial machine vision tool in the 1980s was called blob analysis (the term is still used but describes something of much greater complexity, and is well beyond what 1980s hardware was capable of). The idea was that if one can arrange to image an object so that it can be separated from its background by brightness, then one could quickly and accurately determine the object’s size, position, and orientation. For example, an object might be backlit so that it appears dark with a bright background. The number of industrial applications where such imaging could be arranged was very limited, so more powerful tools like Search were more valuable. But customers expected a vision system to have a blob tool, and the 68000/VM7 system could do it faster and more accurately than any previous system.

In the earliest days of industrial machine vision (early 1980s) blob analysis used binary images, where a brightness (graylevel) threshold produced 1-bit pixels representing background or object. The size of an object was just a count of object pixels, i.e. area. The position was the center of mass of object pixels, and orientation was the angle of the first principal axis of inertia. Here’s an example:

This is a synthetically generated binary image, very low resolution so you can see the pixels. It’s supposed to be a metal part with a rectangular hole in the center and two circular holes. The red lines are the first and second principal axes of inertia, which intersect at the center of mass. The center of mass gives you the position of the object, and the angle of the first principal axis (the longer line) gives orientation. The lengths of the axes are the principal moments of inertia, and are good estimates of the width and height of the object, at least for rectangular objects. The area (number of object pixels) gives you size.

The great thing about these quantities is that they are geometric properties of the object, independent of image coordinates. Center of mass and the principal axes move and rotate with the object, except for some variability due to pixel grid quantization effects.

I mentioned in a previous post that I hate binary thresholds, writing, “Thresholds discard information, and vision is hard enough without immediately starting with much less information than is available.”

Blob analysis is a great example of the value of grayscale processing. This may not be obvious because the whole premise is that we can separate object and background by brightness, so why would we need more than one bit of information in a pixel?

All information about the size, location, and orientation of an object is provided at points where brightness is changing in some direction, i.e. where brightness gradient is non-zero. In a region of uniform brightness you learn nothing. With the imaging setup for blob analysis, all information is at the object/background boundary points. Pixels at the boundaries are not purely object or background, they have brightness values that depend on where the boundary cuts the pixel.

Those brightness values are information. At any given boundary pixel there is only a little bit of information in the graylevel, but averaged over the entire boundary there is a lot. If instead of binary pixels we assign each pixel a weight between 0 and 1, such that 0 is background, 1 is object, and in between is in between, the results are significantly more accurate, and the effects of pixel grid quantization are significantly reduced. For example,

One can think of the mapping between raw graylevels and weights to be a soft, or fuzzy, threshold, for example:

Any desired mapping can be used at no runtime cost, since we’ll use the VM7 T array. The weights from T are integers that represent the 0 – 1 range.

To compute area and center of mass we use:

A = \sum w_i \quad C_x = \frac{\sum w_i x_i}{\sum w_i} \quad C_y = \frac{\sum w_i y_i}{\sum w_i}

Here w_i, x_i, and y_i are the weight and image coordinates of pixel i, and the sums are over all i as usual. For the principal moments and axes we also need these sums:

\sum w_i x_i^2 \quad \sum w_i y_i^2 \quad \sum w_i x_i y_i

I’ll post the formulas if anyone asks to see them. You’ll notice that all of the computations use image coordinates, but if you move, rotate, and scale the coordinates the center of mass and the principal axes are at the same place on the object, and area just scales. That’s the value of geometric quantities. Some quantities, like bounding box, are not geometric and give different results in different coordinate systems, making them much less useful.

Looking at the sums we need, it seems that there are eight multiplies and six adds per pixel. For background pixels (weight = 0) we can skip all the computations, so it’s eight multiplies and six adds per object pixel (weight > 0). We can use the same factorization and moment generation strategy we used for NC to eliminate all the multiplies and reduce the per-pixel adds to three. We won’t skip the background pixels, but with VM7 we can get close to 14 clocks per pixel, plus moment generation time, for grayscale blob analysis.

While the mathematics of the factorization and moment generation strategy for blob is nearly the same as for NC, the computation using the 68000/VM7 system is completely different. In the next post we’ll see how this is done.

[bill75]

We did a lot of business with the Cognex 2000 in Japan, primarily with semiconductor capital equipment manufacturers, and I spent a lot of time there working with Japanese engineers and managers.

On one visit I had been working in the outskirts of Tokyo. While I love Japanese food, after three weeks I wanted a hamburger already. So I popped into McDonalds and ordered a Big Mac and some nuggets. I was halfway down the street with my order when I heard footsteps—someone was running up from behind. I turned and saw the kid who took my order, he must have been all of 15, run up, bow, and hand me a small paper bag. Then he turned and sprinted back to his post. Inside the bag was a single container of barbeque sauce that he had apparently forgotten to include in my order.

The 1980’s were the time that Japan really began to flex its economic muscle in things like autos and consumer electronics. Some in the US accused Japan of unfair trade practices, but what I found were serious people obsessed with quality and customer service. Of course they made great cars.

One time a Japanese customer of ours complained because a shipment had arrived in a damaged box. The 2000 inside was fine, and we figured that the box had done its job, protecting the product inside. But the customer replied, “We ship our toys in better packaging.” We strengthened our boxes.

Evenings were filled with eating, drinking, and smoking. And drinking and singing. And drinking. Once I was scheduled to give a talk at 9:00 AM about the 2000 to a roomful of engineers. I was so drunk the night before that I was at least an hour late to the meeting room. I figured that the people would just go about their business until I managed to drag myself in, but no. They all had waited patiently in the meeting room until I arrived. Would be disrespectful to leave.

Once at lunch with a half dozen people I ordered a diet coke. What I did not realize is that soda is for kids. Adults at business lunches drink tea or beer, maybe sake. My lunch companions were worried that I had embarrassed myself, so they all ordered a diet coke. This was explained to me much later.

What a culture!

[drogon]

@bill75

What a culture!

I was involved briefly with a Japanese customer while I worked for supercomputer co. in Bristol (late 80s) and we were briefed on etiquette and how to deal with visiting engineers and dignitaries. Simple things like presentation of business cards (I was doing a lot of origami at the time and made some pretty business card holders which seemed to go down well)

And we took one of the visiting engineers out a few times - one to a karaoke bar where he sung “Imagine” and if you closed your eyes it might well have been John Lennon on the stage - the whole place was utterly entranced. Turned out he was the president of his local karaoke club back home…

Not sure that culture still exists, but yes, what a culture.

They hadn’t learned how to make scotch that didn’t taste like fire-water though…

-Gordon
ps. They were using the system we shipped out - the biggest to date - to pick the right colour for their next car… High resolution 3D imaging then it calculate the paint formula

[bill75]

Recall the sums we need for grayscale blob analysis:

\sum w_i \; \sum w_i x_i \; \sum w_i y_i \; \sum w_i x_i^2 \; \sum w_i y_i^2 \; \sum w_i x_i y_i

For NC we factored the sums on the model values, summing up in C[i] all of the image values that corresponded to model value i. For blob we’ll factor on the x and y coordinates of the pixels, summing up the weights for each x coordinate and for each y coordinate.

The pixels with a given x coordinate correspond to a column of the image. Summing all the columns is a projection of the 2D image onto the x axis. We can write this

P_x[k] = \sum_{i|x_i = k} w_i = \sum w_i \delta(x_i – k)

Here \delta is the discrete delta function

\delta(n) = \begin{matrix}1 \; \text{if} \; n = 0 \\ 0 \; \text{if} \; n \neq 0 \end{matrix}

Or equivalently, using the T array to map pixels to weights

for (int y = 0; y < height; ++y)
  for (int x = 0; x < width; ++x)
    P[x] += T[image[x, y]];

Projecting the image onto the y axis is similar. In general we can project a 2D image onto a line at any angle, although we will not need to do that here. (Accurate and fast projection is challenging in the general case due to pixel grid effects; the best way to do so is here.)

With an x and y projection we can do moment generation by cascaded accumulators to get every sum we need except one: \sum w_i x_i y_i. To get that final sum we’ll project onto a line at 45 degrees, which is just summing along diagonals. Pixels along a diagonal have coordinates such that x \pm y is constant. Therefore

\sum w_i (x_i – y_i)^2 = \sum w_i x_i^2 \; – 2\sum w_i x_i y_i + \sum w_i y_i^2

Moment generation gets the sum on the left, and since we know \sum w_i x_i^2 and \sum w_i y_i^2 we can get \sum w_i x_i y_i .

Now that we’ve got the math out of the way, let’s see how to arrange the projections using the 68000/VM7 system. The first step is to determine a map from image graylevel to weight. This can be done by analyzing a histogram of the image. If we load the T array with the identity map and touch every image pixel with the image code in addresses bits 23:22, the E array will be a histogram. Compute the desired map and load T. It doesn’t really matter what’s in the M FIFO. This is image-only mode, three clocks/pixel.

The y projection, sums of rows, is easiest. Load 8 zeros into the M FIFO and run VM7 in image-only mode. For each image row, touch each pixel with a cmpm.l, dealing as necessary with row length and alignment. At the end of each row the sum is in C[0], read it out and store it. Three clocks/pixel.

The equivalent for the x projection, summing down one column at a time, is extremely inefficient. One efficient method is to sum eight columns at a time. Load the values 0 – 7 into the M FIFO and execute this for each row in a set of eight columns:

cmpm.l (a0)+,(a0)+
adda d0, a0

That’s 28 clocks for 8 pixels, 3.5 clocks/pixel. We can actually do slightly better using four address registers for image pixels and one for model pixels:

cmpm.l (a0)+,(a0)+ ; load M FIFO for next eight columns
cmpm.l (a1)+,(a1)+ ; first row
cmpm.l (a2)+,(a2)+ ; second row
cmpm.l (a3)+,(a3)+ ; third row
cmpm.l (a4)+,(a4)+ ; fourth row

Here we touch four complete rows, with the projection ending up in C. Since C has 256 elements, if rows are longer than 256 we do the image in strips 256 columns wide. 100 clocks for 32 pixels, 3.125 clocks/pixel. Handling row size and alignment is annoying but not too hard to arrange.

To understand diagonal projections, let’s consider a simplified example where the C array has eight elements and we’ll process the image in strips of eight columns. Here is one such strip showing which projection bin corresponds to each pixel, along with model values we’ll use:

Model values:

We’ll operate VM7 in image/model pair mode. Process the first row, projection bins 9 – 16 in this example, with the M FIFO loaded with 0 – 7 from the above M values, starting at the highlighted one. At the end of the row, projection bin 16 is in C[7], and we’re done with that bin for the current strip. Read it out, add it to any previous bin 16 that has been stored, and zero it.

For the next row, use the M values starting one before the highlighted one, 7, 0 – 6. The first image pixel in this row, for projection bin 8, is added to C[7], which used to be bin 16. Repeat this for every row in the strip—at the end of each row one bin is retired and reused for the new bin at the beginning of the next row. Five clocks/pixel, with proper handling of row length and alignment.

Grand total 14 clocks/pixel for histogram and x, y, and diagonal projection, although counting the byte-serial carries and some overhead it’s more like 15 in practice. It takes a lot of carefully constructed assembly language, but in industrial machine vision speed is indispensable–if you can’t keep up with factory equipment, you’re useless.

[bill75]

In the first post I wrote that the VM7 technology is “quite obsolete in 2026 for its original intended purpose.” It’s not just VM7—I am obsolete. The skills I cultivated, over four years studying vision in grad school followed by 43 years at Cognex, are obsolete in 2026 for the original intended purpose. And I am totally OK with that.

VM7 is obsolete for a number of reasons. In 2026, multiplying integers is much less expensive than a read-modify-write to memory, as VM7 did. I quantified efficiency by counting adds and multiplies, but completely ignored the cost of doing the read-modify-write. That made sense in 1986, but it no longer does.

Normalized correlation for alignment was replaced by more powerful tools, starting in 1997 with Patmax. These newer tools, taking advantage of SIMD instruction sets, were more accurate and could handle rotation, scale, and non-linear brightness changes, with no special-purpose hardware. Other tools from the early days, like blob analysis, declined as vision tasks grew in complexity.

I am obsolete because constructing clever algorithms and writing screaming fast assembly simply can’t compete with neural nets running on GPUs. There may well be some remaining corners of the “rules-based” vision world that survive (Patmax survives), but what these big models can achieve stuns me. I point my phone at a panel on my furnace and the model finds the label, finds the marking on the label that correspond to the serial number, and tells me the month the unit was made. I have no idea how to do the vision part of that, because there are practically no constraints to base rules on.

Frankly I’m enjoying being obsolete. Much less stress. Time for the next generation to chart their course. I’m happy just to write code for my own amusement and play pickleball.

[EdS]

I do like the idea of getting a result with fewer multiplications - regardless of whether that’s still a good idea today. From a retrocomputing and from a computer history perspective, it’s interesting.