Aligning Diff Output

‘Bots are off limits this week so here is a story from this year’s Iverson College – a fantastic week spent in the company of a wonderful mixture of array and functional language gurus and newbies, all learning from each other. One evening, Dhru Patel presented a problem that he was working on which involved displaying the results of a “diff” side by side with the matched rows aligned. For example, the input might be:

      OLD NEW
┌────────┬────────┐
│This    │This    │
│is the  │original│
│original│is not  │
│text    │        │
└────────┴────────┘

Edited by Yoda, the text was. The selection of rows to be aligned requires finding the longest sequence of rows from the original data that matches rows in the edited data without ever skipping backwards through either sets of data. In this case, it is the original first and third row, matching the first two edited rows. We will return to how we might identify these rows in a future blog entry (meanwhile, try to grok John Scholes’ YouTube video on Depth First Searching and think about it). For now, we will provide this information as a left argument, a vector of Boolean vectors that marks the location of the matched rows:

      (1 0 1 0)(1 1 0) AlignMatched OLD NEW
┌────────┬────────┐
│This    │This    │
│is the  │        │
│original│original│
│text    │        │
│        │is not  │
└────────┴────────┘

At Iverson College there was general agreement that “there should be a non-looping solution”, and Devon McCormick immediately stated that he would bet that it involved grade (). Let us explore:

      masks←(1 0 1 0)(1 1 0)
      ⎕←matched←∊masks ⍝ The two match masks catenated together
 1 0 1 0 1 1 0 
      ⎕←origin←(≢¨OLD NEW)/0 1 ⍝ 0 for items from the old array, 1 for new
 0 0 0 0 1 1 1 
      ⎕←block←∊+\¨masks ⍝ running count of matched rows
 1 1 2 2 1 2 2   
      ⎕←data←block,(~matched),origin,OLD⍪NEW
1 0 0 This    
1 1 0 is the  
2 0 0 original
2 1 0 text    
1 0 1 This    
2 0 1 original
2 1 1 is not  

Our goal is to create an expansion mask for each argument; this is going to insert blank lines at the points where a non-matched row from the other argument is included. The next step is to reorder everything by ascending block number, and within each block move the matched rows to the front (ascending by ~matched), as follows:

      ⎕←data←data[⍋data[;1 2];]
1 0 0 This    
1 0 1 This    
1 1 0 is the  
2 0 0 original
2 0 1 original
2 1 0 text    
2 1 1 is not 

This contains all the items from both texts in the order that they would need to appear in the final results. We can extract the reordered flag vectors:

       matched←~data[;2] ⋄ origin←data[;3]

Now, (origin=0) is an expansion mask that would expand OLD to match the above, and (origin=1) would do the same for NEW:

      0 1 {(origin=⍺)⍀⍵}¨OLD NEW
┌────────┬────────┐
│This    │        │
│        │This    │
│is the  │        │
│original│        │
│        │original│
│text    │        │
│        │is not  │
└────────┴────────┘

To align the matched rows, we need to eliminate inserted blanks that correspond to matched rows from the other side:

      0 1{((~matched∧origin≠⍺)/origin=⍺)⍀⍵}¨OLD NEW
┌────────┬────────┐
│This    │This    │
│is the  │        │
│original│original│
│text    │        │
│        │is not  │
└────────┴────────┘

In the final function, which collects the relevant lines of code from our experiments, we do not create the temporary “data” matrix, but reorder the origin and matched vectors individually – and instead of doing grade up on a two-column matrix, we compute an integer vector that will sort by descending matched within ascending block (because we know that grade up on a simple small-range integer vector will run like greased lightning):

 AlignMatched←{                ⍝ align matched rows of 1⊃⍵ and 2⊃⍵
     matched←∊⍺                ⍝ matches are marked by 1⊃⍺ and 2⊃⍺
     origin←(≢¨⍵)/0 1          ⍝ identify origin of items in matched (0=old. 1=new)
     block←∊+\¨⍺               ⍝ running count of matched rows
     order←⍋(2×block)-matched  ⍝ Order so matching rows are adjacent and order of
     (origin matched)←(⊂⊂order)⌷¨origin matched ⍝ items following matched row is preserved
     0 1{((~matched∧origin≠⍺)/origin=⍺)⍀⍵}¨⍵ ⍝ Expand exluding matched from "other" list
 }

 

Reviving Lost Arts

The algorithm above makes use of techniques that were well-known in APL circles in the 1980s, but atrophied after nested arrays arrived on the scene and applications tended to keep parts of the data in separate leaves of an array rather than using simple data structures.

If you would like to read up on some of the old techniques, you might enjoy browsing the FinnAPL Idiom Library, and Bob Smith’s immortal Boolean Functions and Techniques. Although nested arrays might have made them a little less relevant in the 90s and 00s, the search for high-performance parallel solutions could bring them back, as explained in this session from Dyalog ’12, on Segmented Scans and Nested Data Parallelism by Andrzej Filinski.

The Blog is Back!

It is now 3 weeks since we shipped Dyalog version 14.0 and released the new Dyalog web site, so it’s probably time to stop celebrating and get back to work. The ‘bot batteries have been recharged and the ‘bots are learning to work as a team using v14.0 futures and isolates. That’s all I can say at this time as the ‘bots are rehearsing for a gig at the J Conference on Friday 25th July and I have been sworn to secrecy until after the show.

Bots 00 and 04 preparing for the J Conference and thinking about whether to attend the IPSA 50th renunion on October 4th

Bot 04 and Bot 00 hanging out in Rochester NY rehearsing for the J Conference and considering whether to return to Toronto with me for the IPSA 50th reunion on October 4th this year.

The next major step in the robot project is to make use of the tiny red board attached to Bot 00 (on the right) – an MPU-6050 accelerometer. At the Dyalog Seminar in New York last Thursday I finally had the pleasure of meeting @alexcweiner in person, and we vowed to crack this nut together; since @romillyc has promised to join in as well, failure is not an option. Stay tuned to hear more about that adventure in the weeks to come!

Welcome to The Development Team Blog

The really good news is that this blog is no longer simply “the CTO blog” but a blog that will be shared by the entire development team as well as invited guests. We look forward to sharing details of the things we are working on with you all…

APL-Controlled Robot Performs Death-Defying Stunts Using PiCam

Regular readers will remember my whining about the poor precision of both infra-red and ultrasonic sensors. But today, the Raspberry Pi / Dyalog APL – controlled “DyaBot” was observed driving on a dinner table – where the slightest navigational error could mean a 3-foot plunge and certain death! How can this be?

The answer is: the “PiCam” finally arrived last week!!!

Capturing Images with The PiCam

I no longer need to complain about sonar beams being up to 30 degrees wide: the PiCam has a resolution of up to 1080×1920 pixels! So all we need is some software to interpret the bits…First, we capture images using the “raspistill” command:

raspistill -rot 90 -h 60 -w 80 -t 0 -e bmp -o ahead.bmp

The parameters rotate the image 90 degrees (the camera is mounted “sideways”), set the size to 60 x 80 pixels (don’t need more for navigation), take the picture immediately, and store the output in a file called “ahead.bmp”. (Documentation for the camera and related commands can be found on the Raspberry Pi web page.) Despite the small number of pixels, the command takes a full second to execute – anyone who knows a way to speed up the process of taking a picture, please let me know!

In the video, each move takes about 3 seconds, this is simply because each cycle is triggered by a browser refresh of the page after 3 seconds. Capturing the image takes about 1 second, the “image analysis” about 40 milliseconds, so we could be driving a lot faster with a bit of Javascript on the client side (watch this space).

Extracting BitMap Data

Under Windows, Dyalog APL has a built-in object for reading BitMap files, but at the moment, the Linux version does not have an equivalent. Fortunately, extracting the data using APL is not very hard (after you finish reading about BMP files on WikiPedia):

tn←'ahead.bmp' ⎕NTIE 0     ⍝ Open "native" file
(offset hdrsize width height)←⎕NREAD tn 323 4 10 
                           ⍝ ↑↑↑ Read 4 Int32s from offset 10
data←⎕NREAD tn 80 (width×height×3) offset ⍝ Read chars (type 80)
data←⊖⎕UCS(height width 3)⍴data ⍝ Numeric matrix, reverse rows

The above gives us a 60 by 80 by 3 matrix containing (R,G,B) triplets. This code assumes that BMP file is in the 24-bit format created by raspistill; I will extend the code to handle all BMP formats (2, 16 and 256 colours) and post it when complete – but the above will do for now.

Where’s the Edge?

At Iverson College last week, I demonstrated the DyaBot driving on a table with a green tablecloth, using code which compared the ratio between R,G,B values to an average of a sample of green pixels from one shot. Alas, I prepared the demo in the morning and, when the audience arrived, there was much more (yellowish) light coming in through the window. This changed the apparent colour so much that the bot decided that the side of the table facing the window was now unsafe, and it cowered in the darkness.

Fortunately, I was talking to a room full of very serious hackers, who sent me off to Wikipedia to learn about “kernels” as a tool for image processing. Armed with a suitable edge detection kernel, I was able to test this new algorithm on a dozen shots taken at different angles with the PiCam. Each pair of images below has the original on the left, and edges coloured red on the right. Notice that, although the colour of the table varies a lot when viewed from different directions – especially when there is background glare – the edges are always correctly identified:

Edge Detection Examples

Except for the image at the bottom left, where the bot is so close to the edge that the table is not visible at all (and the edge is the opposite wall of the room, ten feet away), we seem to have a reliable tool.

The PiServer Page

The code to drive the bot is embedded in a “PiServer” (MiServer running on a Rasperry Pi) web page. Each refresh of the page takes a new picture, extracts the bits, and calls the main decision-making function. The suggested action (turn or drive straight ahead) is displayed in the form, and the user has the choice of pressing OK to execute the command, pressing the “Nah” button to take a new photo and try again (after moving the bot, changing the lighting in the room, or editing the code). There are also four “manual” buttons for moving the Bot. After testing the decision-making abilities of the code, brave programmers press the “Auto” button, allowing the robot to drive itself without waiting for confirmation before each command (see the video at the start of this post)!

Robot Views Table at Dyalog House

The Code

The central decision-making function and the kernel computation function are listed below. The full code will be uploaded to the MiServer repository on GitHub, once it is finally adjusted after I find a way to attach the PiCam properly, rather than sticking it to the front of the Bot with a band-aid!

∇ r←StayOnTable rgb;rows;cols;table;sectors;good;size;edges
 ⍝ Based on input from PiCam, drive at random, staying on table
 ⍝ Return vector containing degrees to turn and 
 ⍝               #seconds to drive before next analysis

 (rows cols)←size←2↑⍴rgb
 ⍝ First detect edges in each colour separately
 edges←EdgeDetectAll∘AK¨⊂[1 2]rgb
 ⍝ Call it an edge if any r, g or b result is >75% of original
 edges←∨/(↑[0.5]edges)>0.75×1 1↓¯1 ¯1↓rgb
 ⍝ Look for lowest edge in each column 
 table←+⌿∧⍀~⊖edges
 ⍝ Divide into 3 equally sized sectors (left, centre, right) 
 sectors←((⍴table)⍴(⌈(⍴table)÷3)↑1)⊂table
 ⍝ Find the LOWEST edge in each sector
 good←⌊/¨sectors

 :If good∧.>15 ⍝ More than 15 pixel rows of table in all sectors
    r←0,0.1⌈(good[2]-15)÷25 ⍝ Carry straight on for a while
 :Else ⍝ Some sectors have less than 15 pixel rows
    :If 0≠1↑previous ⋄ r←previous 
        ⍝ Once started turning, keep turning the same way
    :Else 
        r←((1+>/good[1 3])⊃45 ¯45),0 ⍝ Turn in "best" direction
    :EndIf
 :EndIf
 previous←r ⍝ Remember last turn for next decision
∇

The function AK (Apply Kernel), and the kernel are defined as follows:

∇ r←kernel AK data;shape
   shape←⍴kernel
   r←(1-shape)↓⊃+/,kernel×(¯1+⍳1↑shape)∘.⊖(¯1+⍳1↓shape)∘.⌽⊂data
∇

 EdgeDetectAll ⍝ Our 3x3 kernel
¯1 ¯1 ¯1
¯1  8 ¯1
¯1 ¯1 ¯1

Note the similarity of AK to the APL Code for Conway’s Game of Life!