DEV Community: Vadim Volodin

High-performance 3D vision - optimizing stereo block matching algorithm, part 1

Vadim Volodin — Sat, 29 Aug 2026 15:24:47 +0000

Hi! When I worked at Synopsys, I optimized algorithms for a specialized embedded vision processor — the kind used in autonomous driving and ADAS. In this post I'll cover how to optimize an algorithm that estimates the distance to objects from a pair of images. It's called Stereo Block Matching, and the prefix sums method is what makes it fast. Done naively, the same algorithm can run more than 100x slower.

The stereo pair

Let's look at an algorithm that estimates the distance from a camera to objects from a stereo pair. A stereo pair can be captured with two cameras pointed at the same spot, like a pair of eyes. It's two images — one from the left camera and one from the right. You can overlay them on top of each other and get a 3D movie. Here's what a stereo pair looks like:

An example of two images. One was taken by the left camera, the other by the right.

We'll represent the distances as a depth map. A depth map is an image whose pixel values encode the distance from the camera to the object visible at that pixel:

A depth map built from a stereo pair

Let's look at the principle behind recovering a depth map from a stereo pair. You can think of the stereo pair as two eyes. Human eyes are also able to judge distances to objects. Let's look at the diagram and try to picture how a person sees.

Schematic view of a stereo pair. A1 — left camera. A2 — right camera. D — object. T — distance between the left and right cameras. Z — distance from the object to the camera plane. X0 — the intersection of the image plane with the line from the left camera to the object. (X0 − d) — the same for the right camera.

Here we have point D — the point whose distance we want to find. Point A1 is the left eye, A2 is the right one. For simplicity, imagine there's a pane of glass in front of our eyes with the image projected onto it. Point X0 is where the glass intersects the line from the left eye to the point, and point X0 − d is where the glass intersects the line from the right eye to the point. Here d is the shift of the object on the right image relative to the left one.

We need to find the distance Z. Let's apply the proportionality relation for the triangles:

The sides and heights of the red and green triangles are proportional.

We get the following equation:

Solving for Z:

The problem is that we somehow need to match what the left eye sees against what the right eye sees, so we can tell they're looking at the same point. In other words, we need to find the points X0 and X0 − d. We'll assume these points lie at the same height. We know the focal length and the distance between the cameras. So the task boils down to this: for every pixel in the left image, find d — how far that pixel is shifted in the right image.

You can read more about stereo vision in this article

Stereo Block Matching

There are several algorithms for solving this problem, and one of them is Stereo Block Matching.

It's based on the idea of finding similar neighborhoods around specific pixels. We'll consider the neighborhoods around two pixels as squares.

For each pixel, we'll go over all possible shifts, compute the sum of squared differences between the left and right images, and pick the square with the smallest sum. The shift of that most-similar square (d) reflects the relative distance to the object.

Pixel neighborhoods in the left- and right-camera images. The number is the light intensity at that pixel. As you can see, the intensities in this example are almost identical.

In this example we can see the two squares don't differ much. To measure how similar they are, we build a new square holding the element-wise difference. The smaller that difference, the better.

Element-wise difference of the pixel values

Once we have the square representing the difference between the two, we can sum up its elements:

0 + 1 + 0 + 1 + 1 + 0 + 2 + 0 + 0 = 5

For a given pixel X0 in the left image, we iterate over different values of d, which correspond to different pixels in the right image. We pick the d that yields the minimum sum, and that will be the distance to the object.

It's worth noting that besides the element-wise difference, there are many other cost functions. But we'll stick with this one.

The naive solution

In the naive solution we just do exactly what the algorithm describes, head-on. We go over every pixel in the left image, trying shifts from 0 up to some number, say 1000. For each pixel in the left image we walk over all the pixels in its neighborhood and, at the same time, walk over the pixels in the right image accounting for the shift. Then we sum up their differences. This is called the SAD (Sum of Absolute Differences) metric:

Remember that we can compute d once we can compute sad — for that we take the d that minimizes sad. And that d is the distance to the object.

So the formula for the distance to the object looks like this:

The disparity for x, y is the d that minimizes sad(x, y, d)

Let's write out the algorithm. For simplicity our squares will be of size 3.

Pseudocode

The code looks like this:

def stereo_block_matching(left_image, right_image):
    height = len(left_image)
    width = len(left_image[0])
    # In the resulting image, pixel values encode the distance to the object
    # (the brighter, the closer)
    result = [[0 for x in range(width)] for y in range(height)]
    for y in range(height):
        for x in range(width):
            best_disparity = None
            best_difference = None
            for disparity in range(1000):
                difference = 0
                for shift_y in range(-1, 2):
                    for shift_x in range(-1, 2):
                        difference += abs(left_image[y][x] - right_image[y + shift_y][x + shift_x])
                if best_difference is None or difference < best_difference:
                    best_difference = difference
                    best_disparity = disparity
            result[y][x] = best_disparity
    return result

Let's look at the complexity of this algorithm. Assuming the image is square with side N, we search shifts from 0 to d, and the compared block is a square of size K, the total complexity is:

The prefix sums solution

If K equals 3, the complexity doesn't look too critical overall. But K is usually larger, since a bigger neighborhood accounts for more pixels and gives higher accuracy. Of course, if you make K too large, the algorithm gets less accurate again. A size of 21, for example, is commonly used. In that case K × K is more than four hundred. If we could get rid of that K × K factor in the asymptotics, we'd save a lot.

The prefix sums method can help us here. The idea is to reuse a sum we've already computed. Right now we compute the sum of differences over a pixel neighborhood, then move on to compute it for the next shift and recompute it from scratch, even though we're only adding a new column and dropping an old one. Instead of recomputing the whole sum, we can recompute only the new and old columns. The idea is the same one used for a box filter. The same thing happens when we move to the next row. We lose part of the already-computed sums; all we need is to add a new row and drop the old one, yet we recompute everything. But we can recompute just the new and old rows.

Column SAD

Now for a more detailed description. Let's introduce a variable column_sad — the summed pixel difference over a portion of a column.

Let's look at an example value of column_sad[x, y]:

Computing column_sad: take the columns in the left and right images

Computing column_sad: the column of pixel differences between the left and right images

In this example column_sad[x, y] equals 1 + 1 + 0 = 2.

The formula for column_sad looks like this:

The column_sad value

Computing column_sad quickly

This variable can be recomputed in constant time using its value from the previous row.

Here's an example of the fast update:

Add the element in the last row, subtract the one from the previous row

Add the difference in the last row, subtract it from the previous row

In this example column_sad[x, y] equals (1 + 1 + 0) + 8 − 1 = 9.

The same column_sad value, only computed faster

Computing SAD from column_sad

Using column_sad for a column, we can easily compute the SAD for the whole square:

Moreover, this sum can also be derived from the previous value:

Here's an example of the fast SAD update:

Add the last column, subtract the previous one

Add the difference in the last column, subtract the difference in the previous column

So, sad[x, y] = ((0 + 1 + 2) + (1 + 1 + 0) + (0 + 0 + 0)) + (3 + 2 + 4) − (0 + 1 + 2) = (1 + 1 + 0) + (0 + 0 + 0) + (3 + 2 + 4) = 2 + 0 + 9 = 11

By first computing the column_sad values for each y, and then, given those, computing sad for the current pixel and shift, we get the following complexity:

You can also notice that the sad and column_sad values for different shifts are independent of each other, so they can be computed separately and, accordingly, we only need to store w memory for column_sad.

The algorithm's code

from PIL import Image

def stereo_block_matching(left_image, right_image):
    height = len(left_image)
    width = len(left_image[0])
    # In the resulting image, pixel values encode the distance to the object
    # (the brighter, the closer)
    result = [[0 for x in range(width)] for y in range(height)]

    column_sad = [[[]]]
    sad = [[[]]]
    block_size = 21
    s = block_size // 2

    for y in range(height):
        for x in range(width):
            best_disparity = None
            best_difference = None
            for d in range(100):
                sad[y][x][d] = column_sad[y][x + s][d] \
                               + sad[y][x - 1][d] \
                               + column_sad[y][x - s - 1][d]
                column_sad[y][x][d] = abs(left_image[y + s][x] - right_image[y + s][d]) \
                                      + column_sad[y - 1][x][d] \
                                      - abs(left_image[y + s][x] - right_image[y + s][d])
                if best_difference is None or sad[y][x][d] < best_difference:
                    best_difference = sad[y][x][d]
                    best_disparity = d
            result[y][x] = best_disparity
    return result

Conclusion

That's it. We've looked at applying the prefix sums method in a rather unusual role — estimating the distance from a camera to objects.

In one of the next posts I'll show how to implement this algorithm even more efficiently on a processor that supports SIMD and VLIW, with a neat trick.

[Boost]

Vadim Volodin — Thu, 15 Jan 2026 21:34:45 +0000

Integrating TON blockchain into Trust Wallet: a case study

Vadim Volodin ・ Jan 15

#blockchain #opensource #software #cryptocurrency

Integrating TON blockchain into Trust Wallet: a case study

Vadim Volodin — Thu, 15 Jan 2026 20:56:22 +0000

I had TON cryptocurrency. I had Trust Wallet. But I couldn't use them together — TON simply wasn't supported.

I could have waited. Instead, I started building.

A few months later, TON was live in a wallet with 130 million users.

The Grant That Almost Fell Through

I noticed that TON Foundation was offering development grants. I applied. Almost immediately, they reached out — we hopped on a call and talked it through.

At the same time, I messaged a friend who worked at Trust Wallet. Together, we set up a group chat: Wallet Core developers, the TON team, my engineer friend, and me.

Then things got complicated.

Trust Wallet has two parts. Wallet Core is open-source and handles transaction signing. After discussing it in our chat, I realized we could contribute there. But there's a second part — app interaction (fetching balances, broadcasting transactions). That's closed-source. Only Trust Wallet's internal team can build it.

And that means: management approval, allocated engineering time, accountability. Trust Wallet can't just say "sure, we'll ship it next month."

TON Foundation had doubts:

What if Trust Wallet never adds it to the app? Why fund the grant?

Eventually, both teams met in the middle. TON approved the grant; Trust Wallet committed to prioritizing the integration. Win-win: a new blockchain and users for Trust Wallet, a new wallet and users for TON.

We started coding. My friend did most of the development — I reviewed and refined. We merged the PR in about a month.

How Trust Wallet Works Under the Hood

Trust Wallet runs on three platforms: Android, iOS, and a browser extension.

At its core is Wallet Core — an open-source library supporting over 130 blockchains. Written in C++ and Rust. It's not just used by Trust Wallet; other major wallets like Crypto.com rely on it too. The library handles:

Private key generation
Address creation and validation
Transaction signing
Smart contract interactions

This is where we added TON.

An Unexpected Bonus: Code from Everscale

Few people know the full story.

Originally, Durov launched TON, with TON Labs handling part of the development. After US sanctions, Durov stepped away — but TON Labs didn't. They continued building a fork called Free TON, which later became Everscale.

Then a new TON Foundation emerged, endorsed by Durov. It's now integrated into Telegram and has taken off, becoming a leading TON blockchain.

Here's the thing: TON Labs did a lot of impressive technical work. Everscale was already in Wallet Core. We extracted the shared code into a module called CommonTON.

That code now powers both Everscale and TON.

What Makes TON Unique

Your Wallet Is a Smart Contract

In TON, a wallet isn't just an address — it's a full-fledged smart contract. Everscale uses the older V3 wallet; for TON, we implemented V4R2.

Transaction Structure

In order to create a transaction from wallet, you have to send a message to the wallet smart contract:

External Message (from user to their contract)
├── header: sender's contract address
├── stateInit: code and data (first transaction only)
└── body:
    ├── signature: Ed25519 signature
    └── signing_message:
        ├── wallet_id, expire_at, seqno
        └── Internal Message (to recipient)
            ├── header: "send Y nanotons to address Z"
            └── body: transfer comment

I won't go too deep here. You can read more about the V4 wallet in the docs — including the source code.

Cells and BOC — A Unique Data Model

All data in TON is represented as a tree of cells (Bag of Cells). Each cell holds up to 1023 bits of data and up to 4 references to other cells.

Here's how we create a cell with V4R2 wallet data:

Cell::Ref WalletV4R2::createDataCell() const {
    CellBuilder builder;

    builder.appendU32(0);                       // sequence_number
    builder.appendU32(walletId);                // wallet_id
    builder.appendRaw(publicKey.bytes, 256);   // public key
    builder.appendBitZero();                   // "no plugins" flag

    return builder.intoCell();  // Total: 321 bits
}

To build a transaction, you assemble these cells correctly: recipient address, amount, comment — all packed into a BOC. Luckily, the BOC serializer was already implemented.

Address Formats

Everscale only has raw addresses:

0:4f6bbb5de550f01a5b73792ceca77d8c933ab396a1e300eb0ab5a5f49a430986

TON also supports a user-friendly format:

EQBPa7td5VDwGltzeSzsp32MkzqzlqHjAOsKtaX0mkMJhq_B

This is a base64 string that includes address type information and a checksum. The checksum helps catch typos in seed phrases.

Why Tonkeeper and Trust Wallet Are Incompatible

The Mnemonic Problem

Standards rule the blockchain world. Much of what originated in Bitcoin is still used today. BIP39 (Bitcoin Improvement Proposal) describes how to derive a private key from a seed phrase. The formula: seed = hash(mnemonic + salt).

By standard, salt = "mnemonic" + password.

In TON, salt = "TON default seed".

The result: the same seed phrase produces different keys in Tonkeeper vs. Trust Wallet. You cannot transfer a wallet between them.

This isn't unique to TON — the same issue exists with Waves, Qtum, and Polkadot (sr25519).

Checksum Validation

Seed phrase checksums protect users from typos — enter a wrong word, and the wallet rejects the phrase instead of generating a wrong address (and losing your funds forever). BIP-39 embeds a 4-bit checksum in the last word. TON requires that hash of the phrase starts with a zero byte. These incompatible methods are yet another reason Tonkeeper and Trust Wallet aren't interchangeable.

Beyond Wallet Core

In addition to the Wallet Core implementation, we provided Trust Wallet's team with code examples: how to fetch transaction data, query wallet state, and more. Also consulted on app integration questions related to TON. Also added blockchain info and the logo to the assets repository.

The Result

We connected the TON and Trust Wallet teams. My friend and I built the integration into Wallet Core. Later, Trust Wallet team integrated blockchain into the apps. The code now runs in Trust Wallet across all platforms.

January 2023 — the PR was merged into Wallet Core.

Numbers:

130 million Trust Wallet users gained access to TON

Code:

TON in Wallet Core — main integration
Jettons (TON tokens) — added later

Grants:

Grant for blockchain integration
Grant for adding Jettons

A few months later, I added Jettons, then moved on to other projects for TON and NEAR. But that's a story for another time.

Occasionally I share notes on development and more on Twitter

I would also like to say thank you to:
Tao Xu, Sztergbaum Roman, optout, Sergei, Viacheslav from Trust Wallet team - for organisation and code review
Kirill from TON Foundation - for helping me manage all of that, Narek - for tech support from TON, Steve Yun - for grant and support
Viacheslav - for implementing the main integration
Vladimir from Trust Wallet - for making it possible and for code review
And to everyone, who contributed to this project