<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Mark Li on Medium]]></title>
        <description><![CDATA[Stories by Mark Li on Medium]]></description>
        <link>https://medium.com/@markli_53154?source=rss-c234db1ed249------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*Rla2v8cgc1CV76d7NYt74w.jpeg</url>
            <title>Stories by Mark Li on Medium</title>
            <link>https://medium.com/@markli_53154?source=rss-c234db1ed249------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 14:48:52 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@markli_53154/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Graph-Cut with CUDA GPU]]></title>
            <link>https://medium.com/@markli_53154/graph-cut-with-cuda-gpu-4d3112d33dce?source=rss-c234db1ed249------2</link>
            <guid isPermaLink="false">https://medium.com/p/4d3112d33dce</guid>
            <category><![CDATA[gpu]]></category>
            <category><![CDATA[cuda]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[computer-vision]]></category>
            <category><![CDATA[image-processing]]></category>
            <dc:creator><![CDATA[Mark Li]]></dc:creator>
            <pubDate>Sun, 29 Dec 2019 19:22:29 GMT</pubDate>
            <atom:updated>2019-12-29T21:50:39.252Z</atom:updated>
            <content:encoded><![CDATA[<p>In this post, I’ll walk you through a method to speedup a graph-cut algorithm with the help of GPU.</p><p>In my recent project, I applied graph-cut to image segmentation. Sometimes, using AI on this matter can seem a little bit of an overkill. What if all you want is to grab the cartoon bear out of a black background? Besides, The headache from model training and tuning always can make you feel like steering clear of AI solutions. What’s more, the result of segmentation largely depends on the training set. However, graph-cut has its own problems; it’s over-sensitive to edges in an image, for example, which makes the result overfit.</p><p><strong>When to Use Graph-cut</strong></p><p>I think for images with below attributes, a generic graph-cut algorithm would be a better fit.</p><ol><li>A sharp shift of pixel intensity from background to foreground</li><li>Foreground parts don’t tangle with background parts too much</li><li>Image is not too blurry</li></ol><p><strong>Performance</strong></p><p>Normally speaking, running max-flow with CPU is not quite efficient. Even though Boykov algorithm can limit the runtime on max-flow to as low as 100ms on a good CPU, the time it takes to construct a graph for hundred of thousands of pixel, with little data parallelization available, can make you scratch your head.</p><p>Using CUDA can lower the runtime for the whole process to as low as a few milliseconds, from contracting graph to create residual graph.</p><p><strong>Constructing Graph</strong></p><p>The graph will look like a grid, witch each node corresponding to each pixel. This rectangular shape of the graph allows us to use 2D array to store information about nodes and edges.</p><p><strong>Weights</strong></p><p>Four matrices with size image_width x image_length will be used to store weights. Note that weight means capacity in a residual graph. For each node, there are edges pointing to four different directions, therefore, we use each matrix to store weights for each direction.</p><figure><img alt="WL, WR, WU, WD are matrices" src="https://cdn-images-1.medium.com/max/820/1*0JoW0Rwfr3fEednNU-1frg.png" /></figure><p><strong>Nodes</strong></p><p>Besides weights, we also needs to use matrices to store a node’s information, such as excess flow and heights.</p><p><strong>Push-Relabel</strong></p><p>Serialized push-relabel on CPU is very slow when image is large, so it’s time to harness the computing power of GPU by executing push or relabel operations on different nodes in parallel. During push-relabel, we simply update the matrices introduced above.</p><p>To avoid data dependency issues, every nodes to push on one direction at the same time. This concept is called “wave update”, introduced by NVIDIA.</p><p><strong>Push</strong></p><p>Push function is written as a CUDA kernel. In fact I have a different push function for pushing at each direction.</p><p>Each kernel thread will be working on the next m nodes in the row (or column if the kernel pushes downwards).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/854/1*6Vaifa2KtpCAr28TvA7t6g.png" /></figure><p><strong>Relabel</strong></p><p>Relabel needs to be called so that more nodes will have their heights corrected to make a push to neighboring nodes, given there is residual capacity left on any of its outward edges. Different from Push, where each thread has to work on multiple consecutive nodes, we can use one thread on updating each node. Relabel does not have to happen on each iteration, you can do it every two iterations if you wish each iteration to be faster.</p><p><strong>Tile-based updates</strong></p><p>For push operation, the graph is split into tiles, each has the same size as a kernel block. Wave updates are done on each tile, and tiles need to sync up before the next push kernel invocation. Before a tile conduct any push, it needs to pick up excess flow pushed to its border from the previous push operation. A tile does not need to do anything if it’s inactive, for how to decide if a tile is active, read below.</p><p><strong>Active Nodes</strong></p><p>A node is active when its height is less than the size of the graph and it has excess flow. A tile is active when any node within it is active. I simply use a mask array to store an active node list, which is updated when relabelling the nodes.</p><p><strong>Global Relabel</strong></p><p>Local relabel simply checks a nodes’ own neighbors for potential target to push to, there is a chance that the flow will never go into the sink but get pushed back and forth instead. To solve this problem and shorten the convergence time, we use global relabel to relabel the heights so that there is always a “pathway” for excess flow to go towards the sink node.</p><p>This process start with BFS operation from the sink node; we check which nodes has residual capacity leading to the sink node, then check which nodes have residual capacity to these nodes. The nodes will be labelled according to how close they are to the sink. Like local relabel, height for each node is updated by one thread. Global Relabel only has to be done once in a while, as it’s a costly operation.</p><p><strong>Convergence Condition</strong></p><p>The whole push-rebel process terminates when no tile is active. The residual graph is complete when that happens.</p><p><strong>Segmentation</strong></p><p>To get the partition of nodes, you simply need to run a BFS on the completed residual graph; BFS from sink to get the reachable nodes, which corresponds to foreground pixels, and the other pixels belong to the background.</p><p>If you are curious about how the code looks like, please check out this <a href="https://github.com/ChainZeeLi/graph-cut">GitHub repo</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4d3112d33dce" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>