Image statistics from a pixel perspective?

Sometimes algorithms talk about the mean or variance of a region of an image. But what do they mean? To obtain a better perspective, it’s best to actually explore some images. Consider the following image in Fig.1.

Fig 1: The original image

We have extracted four 200×200 regions from the image, shown in Fig.2.

Fig.2: Different image regions

Statistics are given at the end of the post. Region B represents a part of the background sky. Region A is the same region processed using a median filter to smooth out discontinuities. In comparing region A and B, they both have similar means: 214.3 and 212.37 respectively. Yet their appearance is different – one is uniform, and the other seems to contain some variance, something we might attribute to noise in some circumstances. The variance of A is 2.65, versus 70.57 for B. Variance is a poor descriptive statistic, because it is hard to visualize, so many times it is converted to standard deviation (SD), which is just the square root of variance. For A and B, this is 1.63 and 8.4 respectively.

As shown in region C and D, more complex scenes introduce an increased variance, and SD. The variances can be associated with the distribution of the histograms shown below.

Fig 3: Comparison of histograms

When comparing two regions, a lower variance (or in reality a lower SD) usually implies a more uniform region of pixels. Generally, mean and variance are not good estimators for image because two totally different images can have same mean, and variance.

Image A

Mean = 214.3
Variance = 2.65
SD = 1.63

Image B
Mean = 212.37
Variance = 70.57
SD = 8.4

Image C
Mean = 87.22
Variance = 4463.11
SD = 66.81

Image D
Mean = 56.33
Variance = 2115.24
SD = 46.0

 

Ghosts in the machine: Why Fortran failed to maintain its hold

Fortran dominated the world of computing in the 1960s, and early 1970s, but even though it is still widely used in scientific circles, it not continue to dominate the programming world. One the core reasons might be the rise of the personal computer in the late 1970s and beyond. People were now able to write programs at home on their (probably quite expensive) personal computers.

Fortran wasn’t popular because it was a compiled language – which meant that in the world of the early 80s, a Fortran program could take 10 minutes to compile on a system which used floppy disks. Once compiled, the Fortran program would offer fast execution.  Interpreted languages on the other hand, were slow to interpret the program, but this likely was less of an issue as interpreted programs were often small enough that the speed they ran at was not an issue. Fortran’s libraries such as the math library also consumed large amounts of memory. The micro world was to be dominated by the easy-to-learn BASIC, and later by the likes of Pascal. This was augmented by the fact that many home systems of the 1980s had a ROM-resident BASIC interpreter, making it easy to write BASIC programs. Fortran did make an appearance in the form of a few compilers for the PC, such as MS Fortran, but just didn’t make the inroads of BASIC, or Pascal, in the form of Turbo Pascal family of languages.

The other issue was Fortran’s unstructured nature. As the industry moved towards structured programming in the early 1970s. the two core languages designed in this context, Pascal and C were making inroads. By the time Fortran became more structured with Fortran 77, the damage had been done. Fortran would evolve and carve out a niche in scientific programming, but would not dominate programming as it had in the 1960s.

Coding: A small note on Cyclomatic complexity

One way of deriving a measure of complexity is by means of the Cyclomatic complexity. This measure was introduced by Thomas McCabe in 1976. This basically treats the programs structure as a graph. What is a graph? Similar in many respects to a flow chart, a graph has nodes (actions), and edges (program flow between actions). If E is the number of edges, and N the number of nodes, and P is the number of connected components (for a single piece of code P is equal to 1) the cyclomatic complexity can be derived using:

C = E – N + 2P

Consider the following program segment, and associated cyclomatic graph:

cyclo_complexity

In this case the number of nodes is 8, the number of edges 9, C=9-8+(2*1) = 3. Works nice for a small program, but I hate to think what a large piece of code would look like!

McCabe, T.J., “A complexity measure”, IEEE Trans. on Software Engineering, SE-2(4), pp.308-320 (1976)

Ghosts in the machine: Algol 60

When Algol 60 first appeared, it heralded a new era for programming languages, one which encompassed the idea of “blocks” of code, amongst other things. So why did such a promising language fail? There are likely a number of reasons.

Firstly, Algol 60 had no I/O in the specification. This meant that when Algol was implemented on a particular machine I/O was added, and so the specifications for I/O differed among implementations. Secondly, the 1960s were awash with new programming languages – everyone wanted theirs to be the next “big thing”. It is harder to compete in this sort of an environment. There was also very little time between the release of Algol 60 and beginning work on its successor Algol 68. Algol may have been more successful if effort had been spent on improving Algol 60, rather than creating a whole new language.

Thirdly, and likely the biggest issue was IBM. Algol 60 made some headway in Europe, but never really established itself in North America. Why? IBM’s US domestic installed market share for computer systems was around 71.4% in the 1960s. Its main competitors, Honeywell and Univac held 8.1% and 9.6% of the market respectively [1]. Algol60 was suppose to take over some of Fortran’s territory, but due to IBM’s dominance, this never happened. In fact Fortran so dominated the industry, that even IBM’s other language PL/I (1964) failed to make any headway. On the business side, IBM adopted Cobol in 1962 as its primary development language.

By the time the tide started to turn against Fortran (in the late 1960s), effected by the surge of interest in structured programming, Algol60 had been usurped by Algol68. Algol68 was too complex a language, and other players in the guise of Pascal (and later C) would take over. Pascal was block-oriented, and structured, and would lead the way for programming in the 1970s. By the time S-algol appeared in the late 1970s, it was over for Algol. Which is a pity, because S-algol showed real promise. Here’s a bubblesort in S-algol.

[1] Arnst, C., “Charts show IBM outran others in ’60s”,  Computerworld, Nov.7, p.57 (1977)

The recursive factorial began life as Algorithm 33

When did the first recursive Factorial program appear? As a non-descript piece of code flagged as Algorithm 33 in Communications of the ACM, Volume 4 Issue 2, Feb. 1961. The code is written in Algol 60, as Algol was the first procedural language to allow recursion (i.e. Lisp allowed recursion, but was not a procedural language).

Strangely enough, the algorithm is so overlooked, searching for “Algorithm 33”  in the ACM digital library does not find it… you have to search manually through the issues online.

Why Algol 68 was weird (and ultimately failed)

Look at this piece of code written in Algol 68, which finds the largest element of an array:

proc max = (ref[,] real a) real:
begin real big := -maxreal
   co assign the maximum real number allowed co;
   for i from 1 lwb a to 1 upb a do
   for j from 2 lwb a to 2 upb a do
   if a[i,j] > big then big := a[i,j] fi
   od od;
   big
end

It summarizes many of the things that were wrong with the language, and likely why it would have been a challenging language to teach people to program in.

  1. It uses a *lot* of acronyms. lwb is short for lower-bound.
  2. It uses control-structure terminators (for bracketing) that are the reverse of something in the beginning of the control structure… but not consistently. For example the for-do loop ends with od, and yet the if-then clause ends with fi. Shouldn’t that end in neht, or should the for loop end in rof? Not the smartest choice in the world.

There are elements of Algol68 that are inherently functional, however on the whole the language is mired by complexity. For example, consider the six forms of coercion (down from eight in the first report), something that would likely overly confuse the novice programmer: deproceduring, dereferencing, uniting, widening, rowing, voiding. Algol68 suffered from (i) being developed by committee – far too many people wanting far too many things incorporated into the language, and (ii) not being implemented widely enough, because implementation was a tricky process.

Check out this piece of code, which calculates a factorial:

Which is not exactly easy to read. Guess they didn’t care much about formatting either – not unusual for the time.

Reading a copy of the “Report on the Algorithmic Language ALGOL 68” might send you into a mild seizure, and even the Algol68 Genie learning guide is not for the faint-of-heart. I think if my first class in programming had involved Algol68, I would not have continued in computer science.

I think Algol 68 is summed up by this quote from  Aldous Huxley in his book Those Barren Leaves: It is the great dead language of the future. By the time Algol68 made its appearance, there were other hounds already barking at the gates… simpler languages that would take the lead.

 

 

Why software is pre-Neolithic

In the Neolithic period, from the 8th to the 4th millennia BC, farm animals were domesticated and agriculture was introduced. Humans had begun the task of designing stone implements to use in their everyday lives, and society changed. It was a monumental shift in the way humans lived and interacted with their environments. The implements evolved over time as designs were refined to improve usability. In many respects software is in its Neolithic phase of development. After half a century of evolution, we have moved from software which was driven by punch-cards to text-commands to graphical interfaces, and now to haptic interfaces. However many software designers have failed to understand the basic principles of how humans interact with everyday devices, and have hence created software, and indeed devices controlled by said software with little notion of what true design really is. There are many parts to the problem, from a misunderstanding of the user experience, to a misunderstanding of user requirements, a desire to design overly complex systems, and a lack of knowledge of how users will interact with a product.

Puzzles that programs can’t solve

We like to think programs can solve everything, but there are a group of puzzles which just aren’t that conducive to algorithmic solutions. Why? Because these puzzles often require some form of visual interpretation to solve. Let’s consider an example.

A student was assigned a task to make a 2″ ∅ hole in a thin sheet of copper.
“I’ll go get a drill and chisel”, said the student to the teacher.
“I see you have a hammer and a flat file. Use those”, said the teacher.

To solve this problem, you have to understand how both the hammer and flat file can be manipulated in order to make a hole in the copper sheet.

The solution involves placing the sheet on a support which has a round hole in it. Hammer the sheet to make a cuplike depression. Turn over the sheet, file off the protuberance, and a round hole remains.

Could an intelligent algorithm figure this out? Probably not. Solving this problem requires some intuition, and an understanding of the tools, and how they can be used.

Why building things is good for you

Sitting in lectures must be boring. It was boring when I was a student, and likely it hasn’t changed much in the intervening 30 years. Yes, we have tried to make lectures more interesting, increased active learning, tried to make learning a more engaging experience, but let’s face it, there is a limit to how innovative they can be. The best solution is to turn the lecture into more of a discussion seminar, and that is sometimes only possible in upper years (and even then in a class of 60-70 that’s a stretch).

So should we spend more time building things, and less time looking at books? Likely. There may be a distinct connection between innovative thought and building things. We have likely concentrated too much on the just using our brains at the expense of manual tasks. High schools use to have mandatory manual training or “shop” classes. In some places they are now under the guise of “Technological Education” classes. That’s a bit of a crock considering how little technology is involved in woodworking. In 8th grade I took a woodworking and metalworking course, and four years of technical drafting hereafter. It provided a basic set of skills to use tools, something which is clearly lacking today. How many people wanting to become a mechanical engineer have ever built anything? Yeah, sure mechanical engineers aren’t going to spend their lives machining parts, but they should have an inkling of how things are built, and be able to build things. You don’t need advanced mathematics or physics to machine something… and you don’t even need to machine using metal – you can machine wood on a lathe too. What about some drafting? Yeah CAD is great, but you have to be able to sketch things in the field – it’s a LOT faster that drawing something on an iPad.

How does this relate to computer science? Well, computer scientists build things too. Some of it is software sure, but a growing portion of these systems involve some form of hardware, or external, physical device that involves some sort of iterative process to design and develop. We would have better products if people understood more about how humans use “things” (i.e. tools, appliances), ergonomics etc. Building things also leads to better problem solving skills.

Abbreviations in programming languages

Ever wonder where those wonderful abbreviations in C came from? You know += ? If you delve into Algol 68, you will notice some of them there.

Until Algol 68 datatypes were mostly indicated as keywords such as integer, real,  character. As the new kid on the block, Algol 68 introduced abbreviations that unlike PL/I were not optional. So integer became int, character became char, Boolean became bool (pity C didn’t make booleans integral from day one). For the novice programmer, this does tend to make programs more challenging to read. It also coined the term void. Algol 68 also allowed datatypes to be lengthened and shortened, in a way which will be inherently familiar to C programmers:

long real, long int, short real, short int, long long real, long long int

See the similarity? Of course it doesn’t end there. Algol 68 also allowed a form of optimization as it relates to operators:

sum plusab x

Look familiar? This is the “plus and becomes” operator, which can also be written as +:=, and in C as += . It’s like a piece of assembler jumping into your code… and the presence of this in the code was meant to signal the compiler that this code can be optimized. There were others of course: minusab, timesab, divab, and overab/modab for integers.