Working in Hong Kong (Part 2)

 

Changing Tack

Beating to Windward Sailing is the art of manoeuvring a vessel to exploit the power of the wind. It is somewhat surprising, and entirely lovely, that this is still possible even when your destination demands that you head directly into the oncoming wind. The wind can be tamed even when it insists on pushing you backwards. Tacking is the name for the type of turn you must perform in order defy the wind’s wishes.

In this post I describe the work I’m doing while I’m here. The last one explained how I got here and, in doing so, described the project I proposed in order to secure the opportunity. If I was working on that same project, an entire additional post to explain what I’m up to would be a bit redundant, so naturally - that’s not actually what I’m doing.

My Options

Here’s what happened: First contact with Professor Wang resulted in us scheduling a skype call to talk about the idea of working together - I was supposed to explain my project and describe the expectations I had of the experience. I was quite nervous, but I happily obliged and after ten minutes or so of discussion Professor Wang graciously informed me that my idea was fun, but not of real research interest, then without skipping a beat began to discuss a different problem he had been contemplating. I was blindsided! But the new problem we were discussing was very interesting. Let me try to explain it.

The problem was to do with fractals. The exact definition of a fractal is a bit fussier than the common usage definition (it is more about a sort of scale-independent roughness). In this article we apply the more common definition: A structure is said to be fractal if it exhibits the property of self similarity.

A Brief Discussion of Fractals

Barnsley Fern

Pictured above is one of the most well known fractals; the Barnsley Fern. Each individual frond looks like a smaller version of the whole thing, this is what we call self similar. Fractals can be dizzyingly complex, but because they follow a pattern, can be described in surprisingly compact ways. Compact representation, complex realisation. That’s a desirable combination. If you were dealing with a very complex, incredibly detailed problem, and you realised that actually there was an underlying fractal pattern to it, you would be liberated from worrying about all the fine details. Then you could just reason about the general pattern, since the behaviour would be the same at every level.

Two examples: I learned yesterday that some image compression algorithms work by identifying areas which can be described by fractals, because doing so simplifies the representation so much. Also, many games use fractal rules to generate elements of the environment, like mountain ranges, foliage etc. for the same reason.

The fern pictured above can be generated by the repeated application of these rules:

Where each function is what we call an affine transformation, meaning they can be described by a combination of a linear transformation and a translation. Affine transformations let you shift and stretch your input in many ways, only dissalowing changes which would cause straight lines to become curved.

Affine transformations generating the barnsley fern

Here you can see visually what those four affine transformations (that were provided in mathematical notation) really describe. Varying the coefficients that define these transformation can produce other fern like outputs and other forms, sometimes natural - often more abstract, too. A gallery of images produced in this way can be found here. One such example is shown below.

Sand Dollar Fractal

The Suggestion

The problem was this: Rather than choosing affine transformations then seeing what image results, is it possible to reverse engineer what the transformations must have been just from the resulting image?

graph LR
  subgraph Not the problem
    a1[Function Defintions]-->a2[Picture of Fractal]
  end
graph RL
  subgraph The problem
    b2[Picture of Fractal]-->b1[Function Defintions]
  end

More specifically the question was: can you write a program that would automate this process? Write a program capable of reproducing input images with great accuracy when they contain fractal patterns.

graph LR
  subgraph What a solution would look like
    A[Input Image]-->B[Computer program]
    B-->C[Reproduction of input image]
  end

That was pretty much the suggestion. I was not downtrodden that the Professor had expressed his disinterest in working on my original suggestion because he criticisms were reasonable (It is more of an exercise in pedagogy and design than a mathematics/ computer science research) and because I was flattered that despite this he was still interested in working with me and immediately suggested an interesting project that was accessible and relevant to me.

The Dilemma / The Conclusion

What about my original project? I secured my place on the scholarship program, at least superficially, for the express purpose of realising that idea. So although the prospect on working with Professor Wang at HKU was very exciting, it was not clear that it was the best thing to do. I asked Professor Wang if it would be possible to compromise and instead divide the time available evenly between work on my own project and on the problem he suggested. He responded that this was in theory possible but not optimal because he would not be able to contribute as much to my project so my being there would be of less use. Very understandable objection! I talked to the scholarship team in York and in the end we decided it was best to take the original offer. The scholarship is actually more about personal development than specific project outcomes. The opportunities to learn and grow as a person by taking this chance far outweighed what was offered by my other options. It still feels a bit wrong to have abandoned my project like that though, so, I have not shelved it completely. I’d like to frame what’s happening as more of a beating to windward sort of situation - and in the end my project will be the better for it.

The Plan

So, that is why I am here and that is what I will be working on. Although is not absolutely required that this is the problem we work the whole time; perhaps if we reach a dead end, find something more interesting, or perhaps even solve the problem to our satisfaction, then we will work on something else. Nevertheless, right now the plan is just to tackle this problem with maximum vitality and then reassess the situation as necessary.

Conceptual level

So, my first thought on seeing the problem was that it was really composed of two separate sub-problems. First, ‘feature extraction’. There is a natural sense that we have, as humans, upon seeing an image - ‘oh it has this pattern’ or, ‘oh, it has that pattern’. When we see a picture of the fern we are immediately aware that the form has structure, and if asked we could describe that structure ‘this frond is like that frond, this stem like the other’. We have an intuition about it. This is not so obvious to a computer. Let’s say you have identified which parts look like copies of larger parts though, what’s left to do is figure out how to encode that information as a set of transformations. This is what I saw:

graph LR
  A[Input image]-->b1[feature extraction]
  subgraph The program
    b1-->b2[transformation inference]
  end
  b2-->C[Reproduced input image]
  b1-.-d1(very difficult?)
  b2-.-d2(not so difficult?)

I have talked to Professor Wang and he agrees that this is a natural way of dividing up the problem, and that it would be wise to begin with that second sub-problem. To begin with the feature identification process can be performed by the user of the program interactively.

Practical Level

I have had a lot of problems choosing the wrong technology in the past. I think I’ve been too ambitious - trying to optimise for learning potential not just practicality, so choosing something slightly too unfamiliar or demanding, or perhaps with poor support. This time I will try to avoid making the same mistake. Practically, that means I will try:

  • Using javascript because I’m more familiar with it,
  • Using python because it’s well supported
  • Using libraries where possible so I don’t keep trying to re-invent the wheel

Additionally, my focus right away will just to get something, anything, up and running as quickly as possible as I have often been guilty of analysis paralysis. Soon (by the start of next week?), I hope to be able to embed a barnsley fern that I have generated myself, ideally in an interactive format.

Obstacles

Generally, thinking of the project as a whole, I see many obstacles. Especially in the second part. For now I’ll focus on the near term.

My primary practical concern was, initially, technology. I had talked to the Professor about what technology he would use to implement a demo of a program like this and he suggested $\texttt{c++}$. I have never used $\texttt{c++}$ before so that did worry me a bit. Researching this approach showed me that it would likely involve learning about a graphics library like OpenGL, which in turn meant learning about graphics pipelines, with shaders and tesselaters, and rasterization. I still want to learn those things but I now see them as secondary to my real target, and perhaps even distractions if I focus on them.

Other than that, I think that the applicability of this approach (entirely affine transformations based) concerns me somewhat. Yes, you can generate many fern like structures this way, even in three dimensions (resulting in a form like a Romanesco cauliflower but these forms are almost too regular, and I think do not really capture the full breadth of self similar structures.

I must say though, once my short term goal was clear (write a simple program in any language which will generate Bernsley-Fern type fractals and allow you to vary the underlying affine transformations), I felt less bothered by the potential difficulties down the road. First, this - then that.

Conclusion

I need to get on with it! Tomorrow I begin.