ContourTracing#

Overview#

Given a binary input image and a list of bounding-box ROIs, the ContourTracing operator walks the boundary of the connected foreground component in each ROI. It outputs the boundary pixels as an ordered sequence of global (x, y) coordinate pairs.

Each ROI should contain a single closed, filled foreground component. The current implementation traces one contour per ROI and does not support holes or multiple disconnected components within the same ROI.

The output tensor stores the traced coordinates for each ROI. The length tensor stores the number of valid coordinate pairs written for that ROI.

The following example shows a generated binary input image with five non-overlapping ROIs and the corresponding output results. Each ROI is no larger than 128x128 and contains one randomly generated polygon.

Figure 1: Sample input image (left) and output results (right).

Input and Output Tensors#

The ContourTracing operator takes the following tensors:

  • Input tensor: A U8 binary image in HWC layout with {imageHeight, imageWidth, 1} shape. Foreground pixels are nonzero and background pixels are zero.

  • Rect tensor: A 4S32 tensor in W layout with {maxRects} shape. Each element is an NVCVRectI {x, y, width, height} ROI that encloses one foreground component.

  • Output tensor: A U16 tensor in HWC layout with shape {maxRects, maxContourPixels, 2}. Channel 0 stores the global x coordinates and channel 1 stores the global y coordinates.

  • Length tensor: A U16 tensor in W layout with {maxRects} shape. lenTensor[r] is the number of valid coordinate pairs in outTensor[r].

Each ROI width must be no greater than MAX_RECT_WIDTH (128) and each ROI height must be no greater than MAX_RECT_HEIGHT (128). The VMEM buffers are allocated using MAX_RECT_AREA (16384) as the size.

Algorithm Description#

The contour tracing algorithm uses an 8-connectivity traversal similar to Moore-neighbor tracing. It first finds a start pixel on the contour, then walks the boundary clockwise by searching the current pixel’s 3x3 neighborhood for the next contour pixel. The traversal continues until it returns to the original start pixel.

Bitmap#

For each pixel, the ContourTracing operator uses its 8-neighbor bitmap to decide whether it is a boundary pixel. The bitmap is an 8-bit value that records the foreground/background state of the eight surrounding pixels in the 3x3 neighborhood. Each bit is set when the corresponding neighbor is foreground.

../../_images/bitmap.png

Figure 2: 8-neighbor bitmap#

The bitmap uses this direction encoding: R = 0, DR = 1, D = 2, DL = 3, L = 4, UL = 5, U = 6, and UR = 7.

A pixel is a boundary pixel when the input pixel itself is foreground and at least one of its 4-connected neighbors is background:

input && ((bitmap & 0x55) != 0x55)

The two cases below illustrate why the boundary test uses the 4-connected neighbor mask 0x55. In Case 1, the diagonal background pixel does not make P a boundary pixel because the contour goes from A directly to B. In Case 2, the top neighbor of P is background, so P is on the boundary and the contour goes from A to P to C.

../../_images/bitmap0x55.png

Figure 3: Why the boundary test uses the 4-connected neighbor mask#

NextDir & PrevDir#

The contour is traversed as an 8-connected foreground boundary. nextDir is the direction from the current contour pixel to the next contour pixel. prevDir is the direction of the move from the adjacent background pixel to the next contour pixel. In Figure 4, the current contour pixel is P, and the next contour pixel is Q. Because Q is to the right of P, the nextDir of P is R. Because the background pixel used to enter Q is above Q, the prevDir of Q is D.

../../_images/prevDir.png

Figure 4: nextDir and prevDir.#

Because the previous background pixel is 4-connected to the next contour pixel, the valid prevDir values are only 0, 2, 4, 6. After taking a foreground step nextDir, the next prevDir is:

prevDir = (nextDir + 2) & 0x6;

With this definition, prevDir has only four possible values, which keeps the direction lookup table compact. It also reduces the number of VPU intrinsics required in the device code.

Direction Lookup Table#

Before tracing starts, the host prepares a direction lookup table for all possible 8-neighbor bitmap values. Each entry is a 16-bit value where every 4 bits represent the nextDir for one prevDir value:

Bit range

Meaning

[3:0]

nextDir for prevDir = R

[7:4]

nextDir for prevDir = D

[11:8]

nextDir for prevDir = L

[15:12]

nextDir for prevDir = U

During traversal, the device uses the current pixel’s bitmap to load the corresponding table entry. Then it uses prevDir to extract nextDir from that entry.

nextDir = (entry >> (2 * prevDir)) & 0xF;

After nextDir is found, it is used to update the coordinates.

To build the direction table, for each bitmap and prevDir pair, the table builder follows prevDir backward to a background pixel, then searches clockwise from that background pixel. The first foreground neighbor found in this search is the next contour pixel.

Implementation Details#

For each ROI, the device code performs contour tracing in three steps:

  1. Generate the 8-neighbor bitmap for every pixel in the ROI.

  2. Find four start pixels from the horizontal and vertical midlines.

  3. Trace four contour segments in parallel and merge them into the final output order.

Bitmap Generation#

Bitmap generation is implemented with the existing 3x3 Conv2d primitive. The device code generates the bitmap in three steps:

  1. Split the input ROI into even-row and odd-row buffers, with zero padding around them. This is required by the Conv2d primitive.

  2. Run the Conv2d primitive with a hardcoded 3x3 bitmap kernel.

  3. Repack the Conv2d result when the ROI width is greater than 64. This is because Conv2d requires the output linepitch to be 128 when the width is between 64 and 128. See the Conv2d code and documentation for details.

../../_images/bitmap-conv2d.png

Figure 5: Bitmap generation with the Conv2d primitive.#

4-Way Table Reformatting#

The trace loop uses vlookup_4hbu to load four bitmap values and vlookup_4hu to load four direction-table entries. These lookup intrinsics expect a 4-way table layout. The device code therefore reformats both the bitmap buffer and the direction table into a four-subtable layout before tracing.

4-Way Contour Traversal#

The trace kernel runs four contour segments in parallel. Each vector lane is responsible for one segment, starting from one start pixel and stopping when it reaches its target pixel.

The hot loop performs:

  1. Store the current contour pixel to the corresponding segment buffer.

  2. Look up the current pixel bitmap and the corresponding direction-table entry.

  3. Extract nextDir from the entry, then use it to update the coordinates.

  4. Check whether each lane has reached its segment endpoint.

../../_images/traceAB.png

Figure 6: Segment traversal from A to B.#

The loop also counts the length of each segment. After the loop completes, the segment lengths are written to a VMEM buffer for the following merge step.

Segment Storage and Merge#

The four lanes write to four different memory locations:

  • Segment 0 writes to the first half of outBuf in superbank C.

  • Segment 1 writes to the second half of outBuf in superbank C.

  • Segments 2 and 3 write to two dedicated scratch buffers in superbank B.

After tracing completes, segment 0 is already at the beginning of the output buffer. The device code then copies segment 1, segment 2, and segment 3 after segment 0 in order, skipping any empty segment. Each segment includes its start pixel but not its end pixel, so adjacent segments do not repeat shared endpoints. This produces one continuous contour sequence in outBuf.

Dataflow and Buffering#

The operator uses:

  • RasterDataFlow for the rectangle (ROI) tensor;

  • SequenceDataFlow for input ROI transfers;

  • SequenceDataFlow for output contour sequence transfers;

  • RasterDataFlow for the contour length tensor.

Input and output VMEM buffers are ping-ponged across ROIs. While the VPU processes the current ROI, the next input ROI can be transferred into the alternate input buffer, and a previously completed output contour sequence can be transferred back to DRAM.

Constraints#

The current implementation has the following constraints:

  1. The operator only supports U8 for input tensors.

  2. The operator only supports U16 for output tensors.

  3. The output tensor must have two channels for x and y coordinates.

  4. The maximum number of ROIs per input tensor is 32.

  5. The width and height of each ROI must be no greater than 128.

  6. Each ROI should contain one closed filled foreground component.

Performance#

The performance of the ContourTracing operator is data dependent. The number of trace-loop iterations depends on the contour length and on how evenly the start pixels split the contour. If one segment is much longer than the others, the other vector lanes finish early, which reduces parallel efficiency.

We evaluated 2-way, 4-way, and 8-way designs, where N-way means using N start pixels to split the contour into N segments. The 4-way design performed best and clearly improved over 2-way. The 8-way design shortened the trace loop further, but its extra overhead removed the benefit. Therefore the current implementation uses 4-way tracing.

The tables below use a 1000x1000 U8 image. Polygon ROIs contain the random polygons shown in the Overview. Comb ROIs contain 2-pixel bars across a central spine, a long contour that splits evenly into the four segments. Unbalanced ROIs contain a block with slots cut into its upper left, so that one segment holds almost the whole contour. Contour Length is the mean number of contour pixels per ROI.

Execution Time is the average time required to execute the operator on a single VPU core. Note that each PVA contains two VPU cores, which can operate in parallel to process two streams simultaneously, or reduce execution time by approximately half by splitting the workload between the two cores.

Total Power represents the average total power consumed by the module when the operator is executed concurrently on both VPU cores. Idle power is approximately 7.6 W on Jetson AGX Orin and 11.8 W on Jetson AGX Thor when the PVA is not processing data.

For detailed information on interpreting the performance table below and understanding the benchmarking setup, see Performance Benchmark.

ROIs

ROI Size

Shape

Contour Length

Execution Time

Submit Latency

Total Power

1

128x128

Polygon

411

0.039ms

0.004ms

9.109W

8

128x128

Polygon

423

0.110ms

0.004ms

9.71W

32

128x128

Polygon

422

0.352ms

0.004ms

9.81W

32

64x64

Polygon

208

0.167ms

0.004ms

9.71W

32

32x32

Polygon

102

0.104ms

0.004ms

9.21W

32

128x128

Comb (long contour)

7940

2.222ms

0.006ms

9.408W

32

128x128

Unbalanced (one long segment)

3470

3.181ms

0.005ms

9.207W

ROIs

ROI Size

Shape

Contour Length

Execution Time

Submit Latency

Total Power

1

128x128

Polygon

411

0.038ms

0.003ms

12.862W

8

128x128

Polygon

423

0.118ms

0.003ms

13.155W

32

128x128

Polygon

422

0.392ms

0.003ms

13.155W

32

64x64

Polygon

208

0.184ms

0.003ms

12.761W

32

32x32

Polygon

102

0.112ms

0.003ms

13.155W

32

128x128

Comb (long contour)

7940

2.497ms

0.005ms

12.55W

32

128x128

Unbalanced (one long segment)

3470

3.579ms

0.003ms

12.449W

References#