DEV Community: Bosley

Active Contours with OpenCV

Bosley — Sun, 20 Dec 2020 01:17:21 +0000

During my last year of my undergraduate studies in Computer Science I did some work with automated drone control using something called Active Contours. The contour algorithm used was the research of my advisor and it was primarily my task to simply take information from said contour and translate it into drone controls. I didn't have to implement the algorithm, but it got me interested in Active Contours (snakes).
A while back while waiting to hear back on a job opportunity I decided to play with C++ and OpenCV in an attempt to get under the hood of these snake algorithms. I knew that the variant we used for the project would be a little bit beyond me until I could nail down the fundamental aspects. During that time I implemented a C++/QT snake algorithm, and it went pretty well.

The algorithm here is kind of lame. Its a simple energy minimization algorithm sourced from this paper.



    Energy = ∫(α(s)Econt + β(s)Ecurv + γ(s)Eimage)ds

Long story short, you take iterate over set of points and select a "neighborhood" of points around each looking for a spot that reduces the overall energy of the contour model.

Having an itch to play with snakes again (a couple years later) I decided I might want to revisit the fundamentals and maybe see if I could make the snake a bit better. I couldn't decided if I wanted to use Rust (which I'm currently in love with) or Python (which would be slower, but a lot easier to get started).

In order to figure out which I would want to do I obviously had to implement both and see which would be my target.

Python

As you can imagine, Python was pretty simple. I used pip to install opencv and away I went. I got the implementation completed in about 45 minutes. It went well, but something about using Python for this task just rubs me wrong.

Rust

Getting started in Rust was a little bit harder. I had to use opencv-rust and fight my Mac a little bit to get things building. Once I got it building I then had to sift through the documentation to see how everything works with the generated rust code for OpenCV. It took a couple of hours but I got it working too.

Next Steps

Now that I've implemented the simple algorithm in C++/Python/Rust I think I can say for certain that I understand well how it works. I'll definitely be continuing with Rust.. I just love it too much. I'm hoping that in the coming months I'll be on my way to making some improvements and maybe even tackle Anisotropic Fractal Snakes.

Building A Virtual Machine

Bosley — Thu, 25 Jun 2020 20:01:21 +0000

Over the last few months I've been making a virtual machine I'm calling Nabla, and I wanted to share some of what I've done.

The Nabla VM is a virtual machine I designed with an idea that started with wanting to make a programming language. I wanted it to be higher level, and I didn't want to just define a grammar and plug it into LLVM. I wanted to really MAKE the language. When I mean "make" I mean, I wanted to write things from top to bottom, and I wanted that bottom to be special. What do I mean by special? I mean that I wanted the bottom-most layer of the language to be an executable byte code so I wouldn't have to target different platforms. I figured making a VM that executed byte code aught to be easy enough.

Stack Based, or Register Based?

As I started to investigate what the world was doing with VMs I noticed that there were two primary types of VMs that languages leveraged to perform their operations. Stack based, and Register based. There is an article here talking about the two, but basically it comes down to the means by which you move data around. Do you use a stack, or pre-defined locations for storage (registers). I only thought about this for about 5 minutes before deciding that what I wanted was something... more similar to actual computer architecture. Now I'm not claiming that the Nabla VM represents 1-for-1 physical computer architecture, but it is definitely more similar to that than a simple stack. Realistically, while designing the VM around this register idea, it is kind of pointless to make a distinction when it comes to the Nabla VM. It does in fact use registers, but it also leverages stacks for computation... as do most things.

So what does this Architecture look like ?

I'm glad you asked. The Nabla VM was built around a concept I've wanted to play with for a while. The concept of physical distinction between data and instructions. Usually when you have assembly code everything is stored in the same place and executed sequentially. Instructions and data are in the same area so fun things like stack smashing / stack overflow can allow mischievous users to overwrite code in memory and execute their own routines. With a physical distinction between data and instructions, we can mitigate some (only some, the idea is not bullet proof) of the attack vectors that people could use to poke and prod around on a machine.

Now, being up front, the Nabla VM isn't meant to be secure or anything fancy like that. I just wanted to take that idea and have it influence my design. I realize that the VM exists on a regular machine and the distinction I'm making between instructions is just a facade.

I decided that there would be physical areas that separated out functionality of code such-that these areas' data could even be separated. Now, in order for these distinct things to communicate they needed methods to transfer information. As discussed earlier, I decided to go with a register based VM, so obviously there are some registers, but what about big swaths of data? With this in mind I decided to add a global area for shared data storage. Wild! Making things even more crazy, I added stacks to each of the function units so they could process data without leveraging the storage stack for arithmetic calculations. This will make sense later on when I start to cover the pseudo-parallelism that the VM can do.

So what does this thing look like ?

Stunning!

I gave the machine 16 registers, a global stack (GS), function units (FU), and stacks local to a function unit (LS).

Instruction Picking

So now we have a box. With boxes in it, and in some cases, another layer of boxes. Now we just need a stick to poke them with and make them do things. This stick of course is an instruction set. Now when it comes to instruction sets there are a few overall ideas called RISC CISC and MISC that I got to choose from. What a world! These stand for "Reduces Instruction Set Computing," "Complex Instruction Set Computing," and "Minimal Instruction Set Computing." The gist of what these mean is that I can either have a literal metric ton of instructions (CISC), a reasonable amount of instructions (RISC), or barely enough to do anything more than basic computation and we'll have to to tons of execution do do literally anything (MISC). My descriptions here are clearly biased by my opinion, and it should be clear that I chose RISC. Mostly because I didn't want to write all of the instructions, but also because lots of types of instructions in a virtual environment would have a detrimental impact on the execution cycle (it would be slower).

Armed with the idea that I wanted a 'reasonable' amount of instructions I started writing out the things I would need to facilitate computation in / with the boxes above. As I started the project I realized that I also needed to decide that weather or not I would have fixed-width or variable width instructions. There are pros and cons to both, but ultimately I decided to go with fixed-width 64-bit instructions (for execution.) Why 64-bit? Primarily because I could stuff a whole lot more information directly into the instruction set with 64-bits than say, with 8, 16, or 32 bits. Why not 128 / 512 ? Because thats ridiculous, and because I didn't need that much space. A lot more space would have been wasted.

The Instruction Set

The instruction set documentation can be found here. I don't want to go into too much detail about the instruction set here, but this is an example of the ASM that the Nabla VM can run:

.file "Example"
.init main

.int8 my_gs_int 24 ; Special instruction to load a value into GS on init

; This 'function' represents one of the yellow boxes above
<main:

    mov r0 $42     ; Load 42 into register 0
    pushw ls r0.   ; Push the entire register into the local stack
    pushw gs r0.   ; Push the entire register into the global stack
    ret
>

As you can see, the instruction set specifies things like which of the boxes above to store data, but what you don't see is that the instructions themselves reside outside of the data storage areas! You can't access the instructions at run time at all. Beautiful.

What about File IO and Networking?

Good question. There is no use in a programming language if you can't load data to/from disk, or chat online with it. For these things I made it possible to extend the VM using devices. The use of these get a bit heady, but in brief, they have their own instruction set (like drivers) that need to be formed within the ASM its self. What do I mean? The byte code that the devices actually executes has to be written in the Nabla ASM. Right now the devices support basic TCP/UDP and IO to disk / stdin and stdout. The networking portion is in line to be beefed up once I get the high level language developed to a workable state. WAIT. Did I just say high level language? Good transition time.

High Level Language

As I mentioned in the start of this post, I wanted to make a programming language. I guess I kind of did by making the assembly language, but that was more of a means to an end. The end being the high level language I wanted to make. Now, I didn't have an idea of what I wanted the language to look like or feel like. I just wanted to do it. So thats what I'm doing. The language "Del" is currently being developed. Its pretty primitive right now, but here is an example of what it looks like :

def add_one(int some_int) -> int {

    return some_int + 1;
}

def main() -> int {

    int my_int = add_one(41);

    return 0;
}

It isn't too pretty yet, but its getting there. As of the writing of this post the language compiles to NablaVM's ASM code and can support ints, doubles, and chars for types, a few different types of loops, and there are some preprocessor directives to import other files.

Right now everything is under heavy development, but you can see the project at its project page here.

Interfaces in C++

Bosley — Thu, 02 Apr 2020 19:23:29 +0000

One thing that I really like using in C++ is interfaces. I wanted to write this up to demonstrate the use of interfaces and maybe help someone figure out when they should use them.

Lets say we have the following program:

#include <iostream>

class AddSomething {
    public:
    AddSomething() {}
    void doOp(int i) { std::cout << "10 + " << i << " = " << 10 + i << std::endl; }
};

class SubSomething {
    public:
    SubSomething() {}
    void doOp(int i) { std::cout << "10 - " << i << " = " << 10 - i << std::endl; }
};

int main() {

    AddSomething as;

    as.doOp(5);

    SubSomething ss;

    ss.doOp(5);

    return 0;
}

This program is pretty lame, but it demonstrates something that happens out in the wild. We have two objects that both take similarly typed data and do different operations on said data.

It looks to me like we could use an interface here. Lets try it.


#include <iostream>

class CoolOpIf {
public:
    virtual void doOp(int i) = 0;
};

class AddSomething : public CoolOpIf {
    public:
    AddSomething() {}
    virtual void doOp(int i) override { std::cout << "10 + " << i << " = " << 10 + i << std::endl; }
};

class SubSomething : public CoolOpIf {
    public:
    SubSomething() {}
    virtual void doOp(int i) override { std::cout << "10 - " << i << " = " << 10 - i << std::endl; }
};

int main() {

    AddSomething as;

    as.doOp(5);

    SubSomething ss;

    ss.doOp(5);

    return 0;
}

So what exactly IS an interface, and why would we type a bunch more stuff to get the same behavior? I'm glad you asked, but before we talk about what interfaces are, we should first talk about the difference between 'IS-a' and 'HAS-a' in terms of inheritance.

IS-a denotes the idea that something IS part of something else. For instance: A human IS-a mammal.

HAS-a denotes the idea that something HAS something else. For instance: A human (ideally) HAS-a brain.

Inheritance helps us define IS-a for an object. In the example above, we defined an an object called 'CoolOpIf.' CoolOpIf doesn't seem so special, but it has a method that can be inherited to make the object inheriting it a CoolOpIf.

So what makes it an interface and not just some other object? Well, the fact that we haven't defined an implementation for CoolOpIf's doOp() method makes it an interface. That means any class that wants to be a CoolOpIf gets to define its own implementation of doOp(), making it a uniquely awesome object with its own behavior.

Now that we know what interfaces ARE, we can explore why we would spend extra time to slap an interface on these objects instead of just doing it the way we did in the first example.

Notice, in the main-line we have :

    AddSomething as;

    as.doOp(5);

    SubSomething ss;

    ss.doOp(5);

You could say that the main-line HAS-a AddSomething and that the main-line HAS-a SubSomething. It is also apparent that we are calling both of them with the same data. Strange. Lets re-write the main-line to leverage the CoolOpIf and see where we end up.

int main() {

    AddSomething as;
    SubSomething ss;

    // We need to use pointers, because the CoolOpIf doesn't have an implementation of its own!
    CoolOpIf * coolOps[2];

    // Assign our objects that classify as 'IS-A' CoolOpIf
    coolOps[0] = &as;
    coolOps[1] = &ss;

    // Loop over them and give them something to do
    for(int i = 0; i < 2; i++) {
        coolOps[i]->doOp(5);
    }

    return 0;
}

We now operate on our objects as a CoolOpIf!
This is where you might be thinking "Why on earth are we still using this interface? The first example worked FINE." You're right! I think it is time to rework this whole thing into something useful, maybe a Publisher-subscriber setup?

You can go here to get the code for this.

First, lets create a SubscriberIf so we can define objects as IS-a subscriber.

    // An interface for objects that want to 'be' subscribers
    class SubscriberIf {
    public:

        // A method that allows subscriber to get some data
        virtual void recvPublishedData(std::string data) = 0;
    };

Since we have an interface all set, lets make some objects that qualify as 'IS-a' subscriber real quick (implementations).

    class SomeSubscriber : public SubscriberIf {
    public:

        // Construct a subscriber and set its name
        SomeSubscriber(std::string name) : name(name) {

        }

        // From SubscriberIf
        virtual void recvPublishedData(std::string data) override {

            std::cout << "Subscriber [" << name << "] received : " << data << std::endl;
        }

    private:
        std::string name;
    };

    // Basically the same thing, but with a slightly different implementation of the interface for demonstration
    class SpecialSubscriber : public SubscriberIf {
    public:

        // Construct a subscriber and set its name
        SpecialSubscriber(std::string name) : name(name) {

        }

        // From SubscriberIf
        virtual void recvPublishedData(std::string data) override {

            std::cout << "Special Subscriber [" << name << "] received : " << data << std::endl;
        }

    private: 
        std::string name;
    };

Next, We'll want to create a publisher object that 'HAS-a' list of subscribers.


    // An object that publishes data to subscriber interfaces
    class Publisher {
    public:

        Publisher() {

        }

        // Check how many subscribers the publisher has
        int getSubscriberCount() const {

            return subscribers.size();
        }

        // We don't want to allow nullptrs, so we ensure the existence of a subscriber by
        // enforcing a reference.
        void registerSubscriber(SubscriberIf & subscriber) {

            // Because we store pointers, and have a reference, we need to make it a pointer so we add '&'
            subscribers.push_back(&subscriber);
        }

        void publishData(std::string data) {

            // Go through list of subscribers, and send them the data
            for(auto &subscriber : subscribers) {

                subscriber->recvPublishedData(data);
            }
        }

    private:

        // We store pointers, because we can't directly store a virtual object
        std::vector<SubscriberIf*> subscribers;
    };

The only thing really different between what we have now and the earlier examples is that our interface now takes a string of data and display it along with some name the're given on construction (subscriber), and we now have an object that maintains a list of interfaces that calls on them when asked to 'publish' some data (publisher).

The only thing left to do is instantiate the objects and drive the publisher.

int main() {

    Publisher myPublisher;

    SomeSubscriber a("Subscriber A");
    SomeSubscriber b("Subscriber B");
    SomeSubscriber c("Subscriber C");

    SpecialSubscriber specialA("wicked");
    SpecialSubscriber specialB("wild");
    SpecialSubscriber specialC("far-out");

    // Since all six of the objects above inherit the SubscriberIf, we can pass them to registerSubscriber
    // that will allow myPublisher to execute the methods made avaiable from SubscriberIf
    // Note: The publisher won't be able to access any methods on the given objects other than those inherited from
    //       SubscriberIf as they are 'sliced' off or 'lost' by us only passing the objects in as SubscriberIfs
    myPublisher.registerSubscriber(a);
    myPublisher.registerSubscriber(b);
    myPublisher.registerSubscriber(c);
    myPublisher.registerSubscriber(specialA);
    myPublisher.registerSubscriber(specialB);
    myPublisher.registerSubscriber(specialC);

    std::cout << "Publisher has : " << myPublisher.getSubscriberCount() << " subscribers" << std::endl;

    myPublisher.publishData("Some data that everyone cares about");

    return 0;
}

Voilà !

We have now made something useful using an interface in C++!

Actionable bitwise with C++

Bosley — Thu, 02 Apr 2020 04:23:16 +0000

I've seen a few posts here and there talking about bitwise operations. I enjoyed reading them, but a lot of the best ones (imo) didn't show great examples of bitwise usage. As someone who leverages bitwise operations everyday at my job, I figured I'd make a post to potentially offer some clarity on the subject by writing up a big example.

Before we get to examples of where we might use this stuff, lets look over the bitwise operations.

If you'd like to see executable code with all of this information, check it out here.

AND

AND-ing two binary values will indicate when corresponding bits in the two inputs are '1' or in the 'on' position.

For example :

    00000101 & 00000011 = 00000001

Here is the same thing, but stacked to give an easier visual representation of what is going on:

OR

OR-ing two binary values will yield a result that tells us if a bit in one input OR a bit in the other input is '1' or in the 'on' position.

For example :

    01001000 | 10111000 = 11111000

Here is the same thing, but stacked to give an easier visual representation of what is going on:

XOR

XOR-ing is pretty cool. Similar to OR, but different in that it requires exclusivity in the input bits being in the '1' or 'on' position. Easily understood as "One or the other, but not both."

    11111111 ^ 00001111 = 11110000

Here is the same thing, but stacked to give an easier visual representation of what is going on:

NEG

Negation! This can be understood as 'flipping' or 'toggling' the bits.

    ~11111010 = 00000101

Again, the stacked example:

    11111010
    --------
    00000101

Shifting

The last thing we will look at before the big example is shifting. Shifting is neat. We basically just push the bits left or right within the binary number.

    0x01      = 00000001
    0x01 << 1 = 00000010
    0x01 << 2 = 00000100
    0x01 << 3 = 00001000

Of course, we can also shift in the other direction!

10000000 >> 5 = 00000100

As you can see, by >> by '5' we've moved the bit 5 spaces to the right. Wicked!

Time for some use-cases (examples)!

These are some cases where we might chose to use bitwise logic.

MSB Checking

This one might seem strange, but there are cases where we might want to see if the far-left bit of a byte is in the 'on' position.


void someFunc() {

    uint8_t var = 0x8A; // In binary, this is : 10001010

    // If we want to see if the most significant bit is set 
    // we can right shift a few places and use it as a bool
    // because 1's are true, and 0's are false. 

    bool isBitSet = var >> 7;

    if( isBitSet ) {
        // Of course, we COULD drop ' var >> 7 ' in as the conditional
        // directly, but for the example I decided not to.

        std::cout << "The bit is set!" << std::endl;
    }

}

Masking

Lets say we have a 32-bit number that represents a color! We all like colors. Why 32-bit ? Because it can happen. Lets say our color happens to be encoded as-follows:

    Alpha = Byte One
    Blue  = Byte Two
    Green = Byte Three
    Red   = Byte Four

Given the following 32-bit binary number, how can we extract these values?

    Alpha    Blue     Green    Red
    10001100 11101001 00001010 00000011

MASKS

We'll use the following masks:

    uint32_t alphaMask = 0xFF000000; // Mask to obtain alpha byte
    uint32_t blueMask  = 0x00FF0000; // Mask to obtain blue byte
    uint32_t greenmask = 0x0000FF00; // Mask to obtain green byte
    uint32_t redMask   = 0x000000FF; // Mask to obtain red byte

Using these masks, we can leverage the functionality of AND to ensure that we get the value we want... and that is pretty great.

    //                     A B G R
    uint32_t abgrColor = 0x8CE90A03;    // The actual 32-bit color

    uint32_t alpha = abgrColor & alphaMask;
    uint32_t blue  = abgrColor & blueMask;
    uint32_t green = abgrColor & greenmask;
    uint32_t red   = abgrColor & redMask;
}

To demonstrate one of these as we did above, lets take the binary representations of abgr and stack it on the blue mask.

10001100 11101001 00001010 00000011
00000000 11111111 00000000 00000000
----------------------------------------
00000000 11101001 00000000 00000000

Hooray! We've discovered that the byte representing our blue color is :

11101001

Chopping!

Lets say we have 32 bits ( a color maybe? ) and we want to send it somewhere. The specification for the protocol that we need to send it over demands we do it 8 bits at a time. Why? I don't know, I didn't write the spec.

In order to do this we need to chop the 32 bits up into 4 bytes and send them sequentially. Then, on the other side, we need to reconstruct the original data.

Its okay, we can do this.


    uint32_t var = 0x8CE90A03;           // This is our color, but in hex 

    uint8_t pack[4];                     // A 'pack' of 4 bytes

    // Using a mask (like above) we grab the data 
    pack[0] = ( var  & 0x000000FF);
    pack[1] = ( var  & 0x0000FF00) >> 8;  // But when we mask some bits we 
    pack[2] = ( var  & 0x00FF0000) >> 16; // need to move them into a range
    pack[3] = ( var  & 0xFF000000) >> 24; // that works within a byte

Explanation

If the masking and shifting seems confusing maybe this will help!
If you recall from the blue byte extraction above we ended up with the following data:

    Byte 1   Byte 2   Byte 3   Byte 4
    00000000 11101001 00000000 00000000

However, uint8_t represents 1 byte. If we attempted to construct a uint8_t with that data, it would be 00000000 as only 'Byte 4' would be used. That means we need to get JUST the data in 'Byte 2' we have to right shift by 16.

      00000000 11101001 00000000 00000000 >> 16 
      -----------------------------------
      00000000 00000000 00000000 11101001

Woot! Now that '11101001' is in the far right we can safely construct a uint8_t and preserve the 'blue' data.

/Explanation

Now that we have a pack of bytes representing our color data, lets just assume we called something to send it, and now we need to reconstruct it as a uint32_t on the receiver end.

This is relatively easy, but not necessarily straight forward.

uint32_t unpacked = pack[0] | (pack[1] << 8) | (pack[2] << 16) | (pack[3] << 24);

We're done!

But what did we do?

We undid all of the chopping of course! We took each byte, and placed them into their corresponding space within the new 32-bit number.

Lets take it step by step.

When we packed the data, masked each byte and put it in the pack. Here is what it looked like:

    initial data = 10001100 11101001 00001010 00000011

    pack[0] = 00000011  // red
    pack[1] = 00001010  // green
    pack[2] = 11101001  // blue
    pack[3] = 10001100  // alpha

As we reassembled the bytes, we followed these steps:

    // Created a 32-bit variable
    00000000 00000000 00000000 00000000

    // Added pack[0]
    00000000 00000000 00000000 00000011

    // Added pack[1] (by or-ing), and shifted it left 8 bits
    00000000 00000000 00001010 00000011

    // Added pack[2] (by or-ing), and shifted it left 16 bits
    00000000 11101001 00001010 00000011

    // Added pack[3] (by or-ing), and shifted it left 24 bits
    10001100 11101001 00001010 00000011

Did it work? Lets check

    Original value: 10001100 11101001 00001010 00000011
    Reconstructed : 10001100 11101001 00001010 00000011

It sure looks like it worked!

Ending remarks

That was a lot of words for me. I don't usually write things for people, but this bitwise stuff is pretty useful and I enjoy it quite a bit.

If you've made it this far and haven't done so yet, you should check out the code I wrote to demonstrate everything.

This was my first article here, I hope I made things clear and didn't goof anything up. If you noticed any mistakes, or if anything is unclear please let me know and I will do my best to clarify things and/or fix them.