Thursday, May 21, 2015

Image convolution with the DFT multiplication property


Determine if image needs to be processed in sections or at once.
If in sections, need to keep track of boundaries (history).

Using FFT


The result of multiplying the DFTs of two matrices is equivalent to taking the circular convolution of one matrix with the other. The larger matrix is the image, the smaller one is the kernel.

Circular convolution in 2D wraps in the horizontal, vertical, and diagonal directions. It would be equivalent to linear convolution by the following image with a 3x3 kernel:


  78 | 2345678
  89 | 3456789
--------------------
  67 | 1234567
  78 | 2345678
  89 | 3456789


The largest square above is the original image. If this image were circularly convolved with this kernel:


1 1 1
1 1 1
1 1 1


The resulting image would be:

array([[39, 27, 36, 45, 54, 63, 51],
       [39, 27, 36, 45, 54, 63, 51],
       [39, 27, 36, 45, 54, 63, 51]])

Performing the convolution with the original image in the frequency domain gives:

array([[51, 39, 27, 36, 45, 54, 63],
       [51, 39, 27, 36, 45, 54, 63],
       [51, 39, 27, 36, 45, 54, 63]])
      
Note that the columns are rotated by one to the right. Linear convolution of images is usually done starting with the center element of the kernel in the upper left corner of the image. This is done so that the output image will have the same dimensions as the input. The boundaries are often zero-padded.

This is only a practical convention, however. True convolution starts with the upper left corner of the kernel - the kernel is flipped in both directions - in the upper left corner of the image. This is analogous to 1D convolution. We have no control over how the convolution is performed when applying the DFT multiplication property. We're contrained by the mathematics: y = IFFT(X*H). So we have to set up the input matrices correctly to get the desired result.

In this case, the linear convolution was performed with the kernel hanging off the edge by one element in every direction. Or in other words, so that the center element (the anchor) was aligned with each boundary element.

On the other hand, multiplication in the frequency domain is equivalent to convolving with the kernel only overlapping the top row or left-most column on the boundary, and with no boundary overlap on the bottom row and right-most column. Again, this is analogous to 1D convolution. Of course, this is circular convolution, so this is just one way of visualizing it. The kernel is really only overlapping the image at all times, and there is no boundary padding.

If linear convolution were performed this way, there would be a pronounced boundary effect only on the top and left edges of the output, resulting in a biasing effect. Typically, we want to balance the boundary effect to all edges.
      
So how do we set up the input matrices for convolution via the Y=X*H property? We want to the output image to be the same as for linear convolution with a zero-padded image, e.g.:


0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 0
0 2 3 4 5 6 7 8 0
0 3 4 5 6 7 8 9 0
0 0 0 0 0 0 0 0 0



We will also need to slice the output image, in order to remove unwanted boundary content and preserve the dimensions. This is directly analogous to removing filter delay from 1D signals.

First of all, the kernel needs to be zero-padded, so that it has the same dimensions as the input image. Otherwise, their DFTs couldn't be multiplied. Some scientific computing packages (e.g Matlab and Numpy) will zero-pad for you, according to the FFT order(s) passed to them.

The simplest way to zero-pad is to place the kernel in the upper left corner of a zeroed buffer. This is what the automatic zero-padding in NumPy will do. That way, after the matrix is flipped, convolution will start with the upper left corner of the kernel. There are other types of padding that can be used, but we'll use zeros for simplicity.

We need to zero-pad the input image in order to preserve the input dimensions in the output. The only difference here from direct convolution is that both image dimensions should be zero-padded to be powers of two, for FFT optimization.

Note that the result of DFT multiplication will be circular convolution with the zero-padded image, not the original, as the algorithm doesn't "know" what part is the original. Remember that circular convolution stops at the bottom and right edges, rather than sliding off them like linear convolution. So we'll want to zero-pad the bottom and right edges the same as for direct convolution: so that the center element of the kernel will overlap the edge elements.

A note here regarding terminology. We'll define "direct convolution" as convolution performed directly, i.e. without any transforms. In "linear convolution" the kernel slides off the edge of the image, without wrapping around. Unless otherwise stated, direct convolution is assumed to be linear.

So for an MxN kernel, the bottom and right edges should be padded with (M-1)/2 and (N-1)/2 (assuming M and N odd) rows/columns of zeros, respectively. We would then pad the upper and left boundaries to make the dimensions powers of two. This will make the slicing algorithm much simpler than if we tried to make the padding the same on all edges.

With linear convolution, we'd only want to remove (M-1)/2 rows and (N-1)/2 columns from the top and left of the output, respectively. This is, of course, analogous to removing filter delay from a 1D signal. It actually is filter delay, we just don't call it "delay" because it's an image instead of a time-varying signal.

For a KxL image, the vertical "delay" will be:
   
    nextpowof2(K + min_zero_pad - 1) - (K + min_zero_pad - 1) + 2*(linear_delay)
   
    nextpowof2(K+M-1) - (K+M-1) + 2*(M-1)/2

    = nextpowof2(K+M-1) - K
   
We start with minrows, which is the number of rows in the image plus the zero-padding, then extend it to a power of 2:

    minrows = (M-1)/2 + K + (M-1)/2 = K + M - 1
   
Not suprisingly, this is the formula for the length of a 1D convolution. Likewise, the horizontal "delay" will be:

    nextpowof2(L+N-1) - (L+N-1) + 2*(N-1)/2 = nextpowof2(L+N-1) - L
   
Again, this is only for odd kernel dimensions.

Note that if we hadn't zero-padded the input image before computing the FFT, it would have "chopped off" part of the right and bottom edges of the output image, when compared to direct convolution. It also would have shifted the image down and to the right, with some unintended boundary effect to the top and left. this boundary effect results from the kernel wrapping around the input image.


Understanding circular convolution on images


To better understand how circular convolution works in 2D, recall that circular convolution is based on the idea of periodicity. So imagine an infinite number of adjacent copies of the image:


  1234567 | 1234567 | 1234567
  2345678 | 2345678 | 2345678
  3456789 | 3456789 | 3456789
---------------------------------------------
  1234567 | 1234567 | 1234567
  2345678 | 2345678 | 2345678
  3456789 | 3456789 | 3456789
---------------------------------------------
  1234567 | 1234567 | 1234567
  2345678 | 2345678 | 2345678
  3456789 | 3456789 | 3456789



If we convolve a kernel with the center matrix, overlapping values from adjacent matrices will create the wrap-around effect discussed previously.

Friday, April 3, 2015

Sailfish OS: A truly open mobile OS?

Like many others, I've often wished that there was a mobile OS that was truly open, or at least closer to it than Android. Something with a user experience more like what you get with desktop Linux.

There is, of course, Ubuntu Touch, but I just haven't been all that impressed with it from a technical standpoint. Moreover, it seems that the Ubuntu project is endlessly setting ambitious milestones that it seldom reaches.

While researching the subject, I came across Sailfish OS, which seemed quite promising. Jolla, the creator of Sailfish OS, makes quite an issue about how much more "open source" their OS is than other more popular Mobile OSes. They even go so far as to call Sailfish an "open source" OS.

Technically, it's quite appealing. It has a swipe driven interface that does more than just take aspects of other mobile OSes and put them in an open source package. It solves a critical problem faced by anyone wanting to adopt an alternative mobile OS, by adding a compatibility layer for Android apps. So what's there not to like?

Well it turns out that, in spite of Jolla's marketing claims, it's not really open source. Here's a graphic showing the proprietary and open source components of Sailfish OS. Turns out that it's really just a proprietary user interface built on top of an open source plumbing layer, which isn't entirely open source either. Even the parts that are open source mostly come from outside of Jolla, most notably the Linux kernel.

So Sailfish, it appears, is really no more "open source" than Android. Perhaps even less so. Here's a discussion in Jolla's user forums that shows the frustration of would-be Sailfish adopters, resulting from Jolla's reticence regarding their plans for open sourcing their product. The comments made in that thread focus on open source as a sort of philosophical ideal. However, I think it overlooks a much more important aspect of open source software: Security.

One of the greatest benefits of open source software is that potential security flaws are scrutinized by so many different people. It's not dependent on the competence of developers within a particular company to evaluate vulnerabilities. It also makes it much more difficult for government entities to coerce developers into creating "back doors" in their software.

What this means for Sailfish, is that it's potentially much less secure than Android or iOS, because of the relatively small number of in-house developers reviewing the code.

Moreover, Sailfish is still a young project undergoing heavy development. But, if something doesn't work, all users can do is sit around and wait for the developers to fix it. What this all means is that Sailfish fails to provide its users with two of the most critical benefits of an open source project.

Perhaps, the one strong draw Sailfish still has is that its app ecosystem is built around Qt and HTML5, instead of Java. However, this is only a partial victory, as Android apps can also be developed with these toolkits, albeit with JAVA dependencies.

So, what does this mean for the future of open source OSes on mobile platforms? Sailfish is still, potentially, a strong contender for the hearts and minds of open source enthusiasts, if they'll provide a clear roadmap for open-sourcing their product, be more upfront in explaining why some components haven't been open-sourced, and do a better job of promoting community involvement.

There's also Tizen which, in spite of the "black mark" it bares because of it's association with big industry, seems closer to being truly open source. However, one major component, the SDK, has a closed-source license.

Of course, there are at least two truly open source alternatives: Ubuntu Touch and Plasma Active. However, they are in many ways technically inferior to the others, at least for now.

The specialized hardware and heated patent wars in the mobile world also present a significant barrier to the propagation of open-source on such platforms. So it may just be matter of giving it time, and waiting for things to cool down. As the mobile form factor becomes increasingly ubiquitous it will likely become more difficult for companies to justify their territorial claims.

For now, Samsung's dominance in the mobile hardware world probably gives Tizen the better chance at becoming a successful mobile OS. But still, it perhaps won't be that long before we see popular community-driven mobile distributions, as functional as Archlinux, Fedora, or Debian are on the desktop. And to that end, I think Ubuntu at least deserves some kudos for its pioneering efforts.

Wednesday, December 3, 2014

CentOS 7 Installer Woes

When I first switched to Fedora from the Ubuntu/Debian world, it gave me such a happy feeling. The installer was the best I'd ever used. It was simple and straight forward, and yet didn't make it nearly impossible to do anything remotely outside the box (ala Ubuntu).
Disk encryption was simple to do. It wasn't some scary forbidden thing, deliberately hidden away somewhere on an alternative install image. Everything felt professional, and well thought out. Not the "work in progress" feel you get with some other distros. Despite all the "Fedora is bleeding edge" hype, I actually found it to be less buggy than Ubuntu, including LTS. And when there was a bug, the folks on Redhat's Bugzilla were usually quick to find a solution.

That was Fedora 17. But it seems like they just couldn't resist the urge to fix something that wasn't broken. If you can get past the installer, though, it's still a great system (unless you use Gnome Shell IMHO).

I really can't think of anything nice to say about the installer. You'd think they would have fixed it before the RHEL 7 release. It's pretty much impossible to install to an existing LVM on LUKS setup. You can unlock the crypt, but it can't find the LVM. Your only option is to rsync all your data to another disk, and start over.

With the direction the rest of the Linux desktop world seems to be going, I find myself liking Archlinux more and more. The installation may take a little more time, but you know exactly what's going on. And you can set up the partitions however you choose.

A GUI should make a task easier and more intuitive, not less. Its purpose is to provide an interface to the CLI that requires less spell checking and manpage reading. Not to abstract it into some clever new paradigm that only the developer understands. That's how the Fedora/RHEL installer used to be. Now it's followed Gnome Shell into the "like a tablet, but not a tablet" abyss.

Monday, June 23, 2014

Recover from failed update in CentOS/RHEL 6

NOTE: It's good idea to tee the output of all of these commands, in case you need to go back and fix something.
If a major update gets interrupted, it can leave the RPM database in a pretty upgly state.

First try to complete the update:
  yum-complete-transaction
 
If this fails, start by removing all the duplicate packages:
  package-clean --cleandupes

If that command exits with an error, manually fix any problems, by updating individual packages, etc. Then re-run. Make sure to watch the output. In particular, write down any config files moved to *.rpmsave, so you can move then back when it's done.

Restore any rpmsave files that need to be.

Now try running:
  yum-complete-transaction --skip-broken
 
There's a good chance this will fail, with a message that the transaction has been disabled.

So re-run the update now:
  yum update

Reinstall the desktop, in case package-clean removed essential packages:
yum groupinstall "Base"
yum groupinstall "Desktop"
yum groupinstall "Desktop Platform"
yum groupinstall "General Purpose Desktop"

Other things you may want to reinstall:
yum install openssh-server
yum groupinstall "Directory Client" (Remember to start sssd)
yum groupinstall "Network file system client"
yum groupinstall "NFS file server"
yum groupinstall "Development Tools"
Anything else important to you. Hopefully you kept a list after setting up the system.

Reboot the system

Reinstall proprietary drivers, as needed.

Hopefully, everything works now. Please comment, if you know of other things that should be done after re-running the update.

Thursday, May 29, 2014

When and how to use exceptions in C++

These are really just some thoughts I wrote down, about how to avoid the mess that can result from handling errors using exceptions. I'm hoping to get feedback, based on the experience of others.

I started thinking about this after reading this blog post by the creator of ZeroMQ.

A function or method should throw an exception under three circumstances:
  1. If there's something wrong with an input argument.
  2. If a required condition isn't met for running the function.
  3. An operating system error occurs, such as a failure to allocate memory, or to access a device or file. This is really a special case of #2.
Therefore, the documentation should clearly specify requirements for input arguments, and the conditions that must exist for the function to execute correctly. It should also state what exceptions will be thrown if those specifications aren't met.

Any other exceptions are the result of bugs in the function's implementation, and shouldn't be included in the documentation. For example, the function may call another function that throws an invalid_argument error. However, if the calling function has total control over the argument being passed, then that exception should never be raised.

Circumstance #3 could be re-phrased as a "system event", rather than a system error. For example, an exception could be thrown when a signal is received and handled by the process.

Saturday, May 24, 2014

Initializing a C++ container with an initializer list, without C++11

This is a common scenario when programming C++. You want to do something that your instincts tell you should be possible, and yet it doesn't work. A quick Google search turns up several answers on "Stack Overflow." However, the answer is almost invariably the same: "Just compile with C++11 enabled."

Well, if you're like me, you seldom have complete control over the restraints for the project you're working on. For example, you may be developing for RHEL 6, and are required by your consumer to use the default GCC compiler version, which is 4.4. Support for C++11 is far from complete in GCC 4.4. Or you may simply not be allowed to use C++11. After all, GCC still lists C++11 support as "experimental."

I've found this particularly frustrating when initializing C++ containers, such as maps or vectors. Pre-C++11, they have to be initialized one element at a time.This can be very inconvenient, and make code look quite messy.

For instance, you may need to keep a table of values, that's initialized at start-up, and remains constant throughout program execution. The preferred way to do this, in my opinion, is to put the table in an initializer list. This can be contained in a source file, where it's used in the declaration of a static global array. It can also be defined as a macro in a header file.  Personally, I like the second approach, because it keeps the source file from looking cluttered, especially for large tables.

But the problem is that, for C++98, this only works with arrays. The closest you're going to get is to first initialize an array with the initializer list, and then use the array to construct your C++ container.

Here's an example that stores a set of tables in a vector. The tables are used to load serial port configuration parameters from a Json file. The initializer lists for the tables are defined as a macros in a header file. LookupTable is a template class used for creating read-only one-to-one maps. Internal storage for LookupTable is handled by a std::map.

#typedef LookupTable<string, unsigned> TermiosFlagMap;

#define MAPINIT(INITLIST) { \
    TermiosFlagMap::mapping temp[] = INITLIST; \
    maplen = sizeof(temp) / sizeof(TermiosFlagMap::mapping); \
    data.push_back (TermiosFlagMap (temp, temp+maplen)); \
}

class TermiosFlagMapMaster: boost::noncopyable
{
    std::vector<TermiosFlagMap> data;
public:
    TermiosFlagMapMaster()
    {
        unsigned maplen;

        MAPINIT (INPUT_FLAG_TABLE);
        MAPINIT (OUTPUT_FLAG_TABLE);
        MAPINIT (CTRL_FLAG_TABLE);
        MAPINIT (LOCAL_FLAG_TABLE);
        MAPINIT (BIT_RATE_TABLE);
    }

    TermiosFlagMap& operator[] (SerialPort::eFlagType type)
    {
        return this->data[type];
    }
} static FLAGMAPS;
#undef MAPINIT


Note that a macro function is used to avoid having to repeat the same lines of code for each table. This deserves an explanation.

A macro can be used to enclose repetitive code that can't be made into a function or an iterative loop. By enclosing the macro definition in a code block (using curly-braces), you get similar behavior to a function, such as restricted scope and variable re-initialization.

For example, you can use it to iteratively perform an operation that requires multiple definitions of an array. Enclosing the macro in a block, causes the array to go out of scope after each iteration, thus allowing it to be redefined and initialized the next time around. The macro argument can be an initializer list, itself a macro. You couldn't do this with a function, because there'd be no way to pass the initializer list to it.

This is useful for initializing C++ containers from initializer lists, even when your compiler doesn't support C++11. You'll typically want to use arrays defined locally in a function, so that their memory will be released when the function goes out of scope. Of course, creating an array, and then copying each element to a container can be expensive. However, in this case the initialization only occurs once at program start-up, and so this isn't so important. 

Saturday, December 7, 2013

Why anti-virus software doesn't make you safer (and may even make things worse)

Even before I stopped using Windows on a regular basis I'd stopped running antivirus software. I'd still run a scan now and then, but not all the accompanying processes that weave their way into every part of your system and siphon away huge amounts of memory and processing power.

Maybe you think I'm crazy, or at least careless. But the fact is, as a software engineer, I realize how easy it would be to write malicious software that can't be detected by an Internet security suite. It would be difficult for even an experienced programmer to find the malicious element in well-crafted code. Software algorithms can be incredibly complex and, contrary to popular belief, computers aren't smarter than humans. In fact, they're incredibly stupid, and they only do exactly what you tell them to do. All antivirus software can do is scan for known threats. It can't detect anything but the most basic attempt at malicious code.

Admittedly, there is some utility in software that watches for attempts by programs to access certain things on your system, or to upload data to the Internet. But everything comes at a cost, and keeping these processes always running in the background slows your computer down and drains battery life. The fact is that most operating systems come with built in security mechanisms, such as mandatory access controls, that are much more effective and don't require running an additional process.Even Windows is quite secure for a well informed user, without additional security software.

On that last point, the real problem is that users aren't sufficiently aware of what kinds of threats are out there, and how to guard against them. As the saying goes, "There is no patch for human ignorance." And therein lies the bane of every IS professional's existence. People think that they can install an Internet security suite, and it will save them, in spite of their ignorance.

Nowadays, operating systems have a lot of these safe guards already built in to them, and much of what third party programs do is redundant. And yet, with all these redundant protections, successful exploitations abound. This is because you can't write software that can sufficiently compensate for the carelessness of users, without making their systems virtually unusable.

The idea that Linux is more secure because fewer people use it is a myth. Besides its technical superiority, a major reason it's harder to exploit is because its users tend to be better informed. Even with strict file permissions, selinux enforcing, and a well configured firewall, I could easily write a script to steal vital information from a Linux system, if the user is foolish enough to download and run it without knowing what's in it.

Don't think you're safe, simply because you use Mac or Linux!

Here's a list of simple things you can do to protect yourself from most Internet attacks, without installing additional software.

1. Don't run as the administrative user. This mostly applies to Windows users, where I believe this is still the default. If you're running as an administrative user, any process you run can basically do whatever it wants to you computer, and access all your personal information. Microsoft has implemented a labyrinth of complicated access controls to try and compensate for this, which could be more easily solved by running as a less privileged user.

2. Don't download and run things from the Internet that you're not sure you can trust. Even if you run them without admin privileges, this only protects your system. It doesn't protect your personal files.

3. Be very careful about clicking on links or opening attachments in emails. Or even responding to them. This is a whole topic by itself, and probably the biggest source of successful exploitations. Spend some time getting informed on the tricks attackers use. Even if you recognize the sender's email address, that doesn't prove who it's from.

4. Use good passwords for online accounts. What is a good password? Well first of all, your name is not a good password! It amazes me how many people think it's crazy not to use anti-virus software, and yet use passwords that are ridiculously easy to hack. Email accounts are a major target, and attackers use automated programs that rummage about the web trying passwords until one works. All while they kick back playing computer games and eating popcorn.

Most people think there's nothing all that valuable in their emails anyways. However, you'd be surprised how much information you can get from emails. Personal information is one of an attackers most useful tools. And because most of the people you know probably use passwords as obvious as yours, your emails give them the names and probable passwords of your family and friends. Once inside your account, they can send emails to everyone in your contact list, in an attempt to get more information. Or they could contain malicious attachments.

The biggest reason people don't use good passwords is because they're difficult to remember. I don't even try to remember most of my passwords. There's no need to. You can store them in a password program, like Keepass, which will auto-generate a complex password for you. Most browsers have the ability to store your password in an encrypted form, and sync them between your computers and smart phone.

5. Lock down your smart phone. This is also a whole topic by itself, so I won't go into detail. This is the computer that people tend to be the least careful with, and yet probably poses the greatest vulnerability; and it's the most likely to be lost or stolen. Most people don't even use a password or pin code to lock their phone, and yet always use one on their desktop. Besides following the tips already mentioned, you should also encrypt your phone's storage.

6. And that leads to the next point: Use encryption. This is one of the least used security measures, and yet one of the most important. At the very least, encrypt all your mobile computers, e.g. phones, tablets, laptops. Passwords do nothing once you have the physical system in your possession. You can read straight from the hard drive without even booting the operating system.

7. Be careful about what information you post on social networking sites.  The more an attacker knows about you, the easier it is to steal your information, and even your identity. Not to mention threats from other kinds of predators.

And remember, "there is no patch for human ignorance." Stay informed about the latest tactics attackers are using. Maybe subscribe to an internet security newletter. And read those emails you get from your company's IT department.