Rick Minerich's Development Wonderland : ideas

Image Processing as Sets of Transformations

RickM — Tue, 28 Apr 2009 00:21:00 GMT

In the image processing world, like most computational problems, we often think our work is composed of only two basic ideas: representation and transformation. Of course, one may have many layers of both representations of transformations and transformations of representations which can make things appear quite complex at times.

However, the problem is much more simple than it appears. This is because a representation can be considered as a transformation from a zero or identity state. Thus, in writing a symbolic language for image processing, we are left with only a single idea to consider: transformations. By composting layers of transformations we can apply image processing techniques in way which is not only bidirectional and platform agnostic but also comes along with a host of other benefits.

Let us consider a simplified example of processing an image:

1) We read in a file (representation) and use a codec (transformation) to convert it into a format understood by our API (representation).

2) We then perform some type of algorithm on that data (transformation) which results in some type of output (representation).

3) Finally, via another codec (transformation), another file is saved to disk (representation).

In most cases there are a great number of intermediate representations. Each is a full copy of the previous iteration with whatever changes have been so far applied. Essentially, the same information is copied over and over again in memory. We do allow for some kinds of in-place processing, however, this is bad as when the operation has been completed, the previous representation has been destroyed.

Instead, what if we batched up sets of transformations? This could have many benefits:

1) The most obvious benefit is that of parallelization. Even at the simplest level of functional composition, these transformations could be handed off to a cluster for asynchronous processing or saved for a later batch processing job.

2) With an intermediate symbolic transformation language, processing algorithms could potentially be combined and reduced to produce a single transformation out of many. This would significantly reduce the processing overhead as well as the number of intermediate memory representations.

3) An intermediate symbolic language which encompassed both codec and processing may make it possible to push the processing transformation through the codec transformation and in so doing no longer need to have any intermediate memory representation. This could provide significant memory and processing speed time benefit.

4) The intermediate symbolic language could be saved into the files themselves thus removing the need for the codec to be present on the end machine. Admittedly, the user would also need the image language interpreter.

5) Instead of applying simple image processing algorithms to an image, the symbolic representation could be appended to the end of the file. This would be quite similar to layers in practice. In this way it would be possible to view the image at all stages of transformation.

6) For large or proprietary transformations, the representation could be kept on the internet and either be downloaded or, in the case where the owner did not want to expose their algorithm, a flattened representation could be sent out and a processing delta could be sent back.

Conclusion

Of course, when I speak of data I don’t only mean the image itself. This technique could also be applied to many classes of data or algorithm. Most notably for us, image metadata.

My initial goal is to build a basic codec representation along with some simple transformations. Currently, I am researching bidirectional, reversible and declarative languages as examples. With F# as a base language I believe it will be possible to build something portable to other ML variants.

How will you parallelize your existing codebase? Try R.A.S.P.

RickM — Tue, 23 Dec 2008 21:23:00 GMT

There has been much talk of how we will be writing all of our new code with parallelization in mind. However, what of our existing code? It’s unlikely that everyone will just suddenly dump decades of existing code and write everything from scratch. In this article I’m going to provide a simple methodology for how we might deal with the ever building problem of parallelizing our existing mountains of code. Comments and contributions are welcome.

Methodologies of the Past

From the STL to .NET, the frameworks we have constructed our applications around have been heavily dependent on the idea of an application having a single thread. Given that the foundation of what we have all been using for a very long time was constructed around this preconception, it’s unreasonable to expect that much of our existing code will ever be fully parallel. Even those that wrote code on top of a thread safe framework may find that years of patches and and poor design decisions make ground up parallelization impossible.

If we set our expectations reasonably, we see that we should instead focus on leveraging parallelism to improve the performance of the slowest parts of our software. From this viewpoint, parallelization is an optimization problem. Like all optimization, the difficulty of parallelizing code will have much to do with the methodologies which were used to write it.

Of course, object-oriented code being written with modern S.O.L.I.D. principles and will be easier to parallelize than older procedural code. At the same time, a poorly organized codebase or poorly written code will always make change difficult and so also hard to parallelize. This is why well written code is worth the investment. We will see the investment paying off in spades for the companies who have bothered to care about code quality. Others who find they have spaghetti code under the hood will find they will need to deeply segregate and modularize before parallelization is possible.

A Methodology for Revisiting the Past

In most cases it would be a poor choice to implement your own threading API. Efficient and easy to use parallelization APIs are coming to (or already part of) every commonly used language and framework. Most of these APIs are not only built on top of years of research, they also have been written and debugged by a large number of people with specific expertise. These APIs are a godsend because they will allow most developers to parallelize existing software with a minimum amount of pain. The parallelization of existing code bases will be much the same as any other kind of performance tuning.

The key will be using a profiler to identify places in the code that would be sped up by parallelization and leveraging these new APIs to take advantage of the available hardware. The exciting part is that this can be done with any existing profiler and many existing APIs. The unfortunate part is that because memory sharing is such a big issue, parallelization requires a degree of separation beyond other types of optimization and so is likely to require some amount of refactoring.

Not all types of performance problems are conducive to being solved by parallelization, careful evaluation of the problem at hand is required. Also, as with anything that requires significant code change, building a solid test fixture is key to introducing as few bugs as possible. By leveraging the ideas of avoiding premature optimization, pragmatic unit testing, using existing APIs, and mindful refactoring it will be possible to introduce parallelization into many already existing projects with a manageable amount of risk.

What is RASP?

While not included in the acronym, the first step in any kind of optimization is profiling. Before you can begin to parallelize your code, you must determine where the bottlenecks might be. A broadly defined list of parallelizable things to look for would be, to quote Rich Hickey, “independent data/work, moderate-to-course-grained work units and/or complex coordination logic that would be simplified with threads”. A couple quick examples of low hanging fruit to be on the lookout for would be slow iterative loops and blocking I/O. It is important to note that as a general guideline it would be wrong to parallelize anything if it would not significantly increase the speed of your software.

For each of the bottlenecks found while profiling, parallelization is best separated into four steps:

Review:	Review code to determine if it is a good candidate for parallelization.
Anchor:	Create a unit test fixture to ensure that the behavior of the to be parallelized code does not change.
Separate:	Ensure that the to be parallelized code has no shared memory constraints.
Parallelize:	Minimally refactor for parallelization while leveraging an existing API to do the heavy lifting.

As the specifics of what each of these would entail depends greatly on exactly which platform and language is in use, I will not go into them deeply now. Overall, it’s a simple methodology but I think both sufficient for the task at hand and broadly applicable.

Conclusion

Review, Anchor, Separate, Parallelize. It’s not intended to be a difficult concept but instead to provide a simple path to parallelization. I would be very interested in hearing about any opinions on what RASP might be missing or how it may be better clarified. While I didn’t have time to discuss them deeply in this post, parallelization patterns are also a key concept in using RASP as if you can’t easily identify what can be parallelized than it would be impossible to use any parallelization methodology. In the future I hope flush out RASP further as well as discuss parallelization patterns in depth.

Avoiding the Dangers of Ambiguously Defined Data-Types

RickM — Fri, 03 Oct 2008 15:10:00 GMT

When you are handed a string, integer, or any value type, can you know what it really represents? Can you define the range of appropriate behaviors for that data? Can you tell if it's formatted correctly? The problem is, in all of these cases, you can't. You can't be sure of it's meaning, it's format or even how to treat it. This is why ambiguous types break the object-oriented programming paradigm and should be avoided whenever possible.

Forward

It's laughable to think that a Physical Engineer or Physicist would work without the aid of units. This is because, when you have undefined units, you can't verify that the thing you get at the end of a computation is defined in a consistent way.

In computing, the counterpart to the Physical Engineer is the Software Engineer. Why is the Software Engineer not held to the same type of design integrity? The use of ambiguously defined variables is one of the largest sources of bugs in modern software development and yet we ignore it. In fact, with many dynamically typed languages we are moving in the direction of more and more ambiguity.

In C# and Java, strings and value types are defined only in terms of their lexical and mathematical operations. Except from the context in which they are used, they carry no additional information about the meaning of their content. In order to perform any non-trivial operation on that data, you have to make assumptions about it's meaning, which in turn leads to bugs.

Is what you are writing really object oriented?

This may seem like a silly question to ask in the modern programming era. Almost everyone is using an object oriented language these days and its mostly taken for granted. However, as any beginning programmer knows, it is very easy to program in an object oriented programming language while completely ignoring the underlying paradigm.

We don't use OO because it's an agreed standard for implementing a programming language, we use it to solve a specific set of problems. These problems are directly related to the modeling of data and data manipulation. Groups of data subtypes are classified into a larger object and operations on that data are defined in such a way as to model behavior in terms of that classification. If the paradigm is ignored these issues become manifest as ambiguity and disorganization.

It follow that using ambiguous data-types in a public API goes directly against not only the object oriented paradigm but also the broader goal of data classification and program integrity.

Why not pass strings and value types as arguments to public methods?

Using an ambiguously defined data type instead of a well defined object means that the domain and formatting of that data is left open to question. It also means that if a user of that data formats it inappropriately it may find it's way into an operation for another type of data and cause havoc.

For a programmer that is familiar with object oriented programming it often comes down to a choice of encapsulation versus convenience. I know as well as anyone that having to define an object to carry your data when you could just pass in a string and a couple of integers can feel tedious. However, by taking the easy way out, you are setting things up to fail down the road.

Consider, is it possible that sometime in the future someone will be using the API you are defining? Will the person looking at that code know the specific format you chose for that string? What about the range of valid values for those integers? What kinds of assumptions about that data will be made that you may have not considered? If they mess up that format or get the range wrong, at what point will it become obvious?

There are a lot of advantages to using objects instead: An object which was designed to carry that same data could verify that it is well defined when it is constructed. It can hand back that data formatted or manipulated in many different ways. You can well defined questions which can be asked about that data which makes program control flow more obvious. Best of all, the code for all of these things is centralized and up to the discretion of the designer of said object. Using a well defined object, two people with different assumptions about that data but asking the same question will get the same result.

Of course, at the lowest level a CPU will be operating on basic value types and so our code will always reflect that to some degree. However, because ambiguous types are extremely dangerous, they should almost always be encapsulated and well defined.

What tools are available to me in .NET?

If you are a .NET programmer the best thing you can do right now is to become familiar with the already existing classes available for making your strings more well defined such as System.Uri and System.IO.FileInfo. I've put up a question on stackoverflow in order to try to build up a list of available container classes.

Beyond the use of predefined classes, it's best to make your own encapsulation objects with heavy up front validation. You can then use extension methods to make native .NET classes take your new validated type. It would be worth putting together a library of free encapsulation classes, structs and extension methods to allow for easy interoperability.

Beware, the .NET Framework encourages ambiguous types.

Unfortunately, as well designed as it is for many things, the .NET Framework is pretty bad about ambiguity. Based on classes such as System.IO.Path and System.IO.FileStream which for some reason take paths represented as strings, you might even say that ambiguity is encouraged. Consider the vast number of methods in .NET classes which take unencapsulated strings and scalar types.

The most unfortunate side effect of this design is that users of the .NET API may come to believe that this is the way things should be in a proper object oriented API. Also, as a consequence, if you want your own product's API to be easily understood by a .NET user you have to follow the same destructive conventions.

F# helps to solve this problem with Units of Measure.

In most object oriented languages, if you were to encapsulate every single scalar value that was passed into a method, it would be quite a lot of extra coding. Microsoft's newest programming language, F#, has a feature called Units of Measure which allows a programmer to optionally specify both meaning and behavior for classes of scalar types.

A scalar with a unit of measure is a real type which is enforced by the compiler. When an operation is performed the resulting type is that of the combined units used for the calculation, just as they would be in physics or engineering. This is because F# is designed in part to be used by engineers and scientists. As a side effect we as programmers get to reap the same benefit.

This type of scalar type classification has long been missing from object oriented languages. It's a huge step forward and I hope other programming languages move to adopt it quickly.

Addendum

@Mark and Jon:

I think I may not have fully expressed what I meant by "handed a string or integer". The context am talking about is post-compilation when variable names no longer have real meaning. In this context (discounting reflection on variable name) all you can tell about an integer is where it is coming from and it's value. An executing program does not have access to documentation.

It's also important to consider reflective programming. It is generally agreed that reflective programming is where the object oriented world is headed. However, when you have a scalar value, you can tell very little about it through reflection. While it is possible to retrieve the variable's name using reflection, actually using the name of said variable to carry type information is a methodology which is extremely prone to errors from mistyping. Errors which will not be caught at compile time and which may lead your program to incorrect paths of execution.

Also, I want to note that while a string is not a scalar value it does suffer from the same type of ambiguity. For this reason it, and other "base" types, should be handled similarly.

IPCV 08' Part 2 - Novel Approaches

RickM — Thu, 17 Jul 2008 17:15:00 GMT

I've managed to rig up Steve's cell to my laptop and I once again have Internet Access. From the time of my last post, most of the talks have been about applications of machine learning. This usually involves a neural network, PCA (Principle Component...(read more)

IPCV 08' - Day One Through One Point Five Rundown

RickM — Tue, 15 Jul 2008 18:03:00 GMT

As you might have seen in Steve's Blog , we ended up getting stranded in Milwaukee overnight and missed most of the keynotes. We did manage to catch the last one which was on a company called Element CXI's very interesting reconfigurable hardware model....(read more)

Comments About Flat Files

RickM — Mon, 09 Jun 2008 15:38:00 GMT

Comments About Flat Files My last blog post got a lot of reddit attention this weekend. I want to thank all of the posters with constructive comments. Open discussion like this is what makes the Internet great. I would also like to take a moment to discuss...(read more)

Why Are Our Programs Still Represented by Flat Files?

RickM — Fri, 06 Jun 2008 19:45:00 GMT

It's time to leave the secondary, external structure of our programs behind. If you can treat the reflected code from a programming language like an abstract data structure, why can’t you just keep the source itself in a similarly abstracted data structure?...(read more)

Top 5 Features Your Cellphone Should Already Have

RickM — Wed, 20 Feb 2008 18:33:00 GMT

Why is innovation dead in the cell phone industry?
This is a list of five innovations I would like to see cell phone manufacturers and service providers bring to market.

1) Timed Silent Mode

How many times has this happened to you:
You go into a movie and like any polite movie goer you put your phone on silent. Then you completely forget about it. A few days later you start wondering why none of your friends have called and start feeling like a social outcast but wait... your cell phone has been on silent the whole time. This is such a simple feature I can not think of any excuse for it not to be on all cell phones.

2) Server-Side Text Message Storage

Shouldn't the 10 cents per message get you something? I mean really, I feel like a little part of me dies every time I pay the cell phone company for the privilege of sending a miniscule bit of text over their network. Also, it's such a tiny bit of data; do we really need to lose it all every time we get a new phone? Also, I know two separate people who have run out of text message space on their phones. This is just ridiculous. Can't they at least use some kind of compressed format? Just keeping the messages stored for you would completely solve this issue. I would even be willing to navigate some kind of web interface to get at them.

3) Accessible cell network APIs.

Are cell phone networks really so exploitable that we should not have access to the guts of our phones? Imagine the kind of awesome innovation could happen by GPLing your phone software and letting programmers have at it. Even a phone with very basic functionality would be wildly popular if people could write their own core applications or operating systems. The free R&D benefit would also be phenomenal. You might see anything from more efficient algorithms for cell tower switching and power management to innovative new interfaces. I wonder if it would be possible to write something that could use tower triangulation to determine your location without having a GPS receiver. The possibilities are limitless.

4) Social Network Integration

How cool would it be if you could just download all of your friend’s phone numbers off of Facebook, MySpace or LinkedIn and just have them show up in your phone? I can see some people saying this would cause phone number overload but that is only because cell phones have such abysmal contact categorization. What if they were placed in easy to navigate categories based on where they came from? Now you might ask, what about privacy? Well, the networks themselves could implement controls to limit who gets your contact information. Imagine being able to have your cell phone automatically have all your business contacts. Now imagine you were the social network site that people had to be a part of to be in everyone’s cell phone business contacts automatically. You could even add a search feature to find people in a certain industry or area quickly. Effectively managing your contacts would suddenly become extremely simple. It’s a huge win for everyone involved.

5) Inter-network Real Time Chat

While text messaging is a good start it has a lot of big problems. We get charged an obscene amount of money to transfer a tiny bit of information. There is no guarantee that the message will actually get to the destination and there is no way to tell. There is a long delay between when the message is sent and when it is received on the other end. Living in the modern day internet age these limitations seem absolutely ridiculous. If the cell networks can support real time audio streams (phone conversations) why can’t they support real time text? The reality of the situation is that the phone companies would rather nickel and dime us with text messages than give us a decent service. Ideally, phone chat would sport these features:

-Fast enough to carry on a conversation without huge misunderstandings developing due to badly timed messages.
-User Status to tell people if you want to be bothered or not.
-Message storage so we can catch up when were in a no service area or our phone dies.
-Supported by the majority of new phones by the majority of carriers.
-Group Chat (Chat Rooms)
-Inline picture uploading would be a nice touch.
-Some internetwork communication would be nice too (MSN, AIM.. etc).

T-Mobile comes close to this ideal with their AIM friendly phones but, unfortunately, there are some major issues with their service. I had a T-Mobile sidekick for a few months and it suffered from two major problems: T-Mobile has mind blowingly awful coverage areas. And not everyone has a sidekick and/or AIM.

This may seem like a lot to ask for. However, I think the majority of people would pay five or even ten bucks a month to be able to chat with their friends at any time. The network load incurred by sending a small amount of text would be insignificant.

What features do you think cell phones are missing?