Skip to main content
Software Engineering

Return to Answer

added 2259 characters in body
Source Link
rwong
rwong
  • 17k
  • 3
  • 36
  • 82

In terms of concurrency and parallelism

If a collection of starting points for contour tracing is supplied, then contour tracing can be run independently by each agent working on one starting point. This is possible because contour tracing is non-destructive on the image or label matrix - it only reads neighbor values around the current position.

However, contour tracing is not data-parallel. In other words, it cannot be vectorized in a SIMD or SPMD machine.

  • Contours can have drastically different lengths. So, some agents will finish early, some will finish late. They will not have coherent flow-control patterns.
  • Also, the memory access patterns will be scattered all over the image. It will also be very wasteful on CPU caches - from each cache line, maybe only up to three pixel values will actually be meaningful for the contour tracing algorithm.

Is there a divide-and-conquer algorithm for contour tracing of a single blob?

I don't know. Please leave a comment if you find one, because I'd like to learn about that too. I haven't done a serious literature search so I may be ignorant. (Of course you should conceal it if it will form the backbone of your thesis.)

On the other hand, I have implemented a tile-based algorithm for connected-component labeling, based on labeling each tile independently and follow up with a "seam stitching" process, and finish off with a final label assignment. It is not data-parallel (not SIMD/SPMD) but it is highly parallelizable - the image can be divided into hundreds or thousands of tiles.

Regarding performance.

In a previous project where I used contour tracing, I was pleasantly surprised that contour tracing algorithms is in general much faster than the execution time for connected-component labeling algorithms, for the type of images I processed, because contour tracing does not perform as many memory operations as would be required by connected-component labeling.

Note that in general, contour-tracing and connected-component labeling aren't direct substitutes for each other - they give outputs in different representations, despite the outputs corresponding to the same blob. You may have to run both algorithms - label the whole image first, sample the "contour starting points", and trace out the contours of each.

Finding nested connected components.

Smoothing the contour coordinates into floating point.

The smoothing of contour coordinates will cause it to change from discrete (integers) to floating point. After that, you will find that the summation of the pairwise Euclidean distance is good enough for most purposes.

The exact detail of smoothing isn't important - for example, you can use Gaussian smoothing, applying it to the sequence of contour X and Y coordinates just like a 1D convolution. Keep in mind the circular (periodic / wraparound) nature of the sequence.

In a previous project where I used contour tracing, I was pleasantly surprised that contour tracing algorithms is in general much faster than connected-component labeling algorithms, for the type of images I processed, because contour tracing does not perform as many memory operations as would be required by connected-component labeling.

The smoothing of contour coordinates will cause it to change from discrete (integers) to floating point. The exact detail of smoothing isn't important - for example, you can use Gaussian smoothing, applying it to the sequence of contour X and Y coordinates just like a 1D convolution. Keep in mind the circular (periodic / wraparound) nature of the sequence.

In terms of concurrency and parallelism

If a collection of starting points for contour tracing is supplied, then contour tracing can be run independently by each agent working on one starting point. This is possible because contour tracing is non-destructive on the image or label matrix - it only reads neighbor values around the current position.

However, contour tracing is not data-parallel. In other words, it cannot be vectorized in a SIMD or SPMD machine.

  • Contours can have drastically different lengths. So, some agents will finish early, some will finish late. They will not have coherent flow-control patterns.
  • Also, the memory access patterns will be scattered all over the image. It will also be very wasteful on CPU caches - from each cache line, maybe only up to three pixel values will actually be meaningful for the contour tracing algorithm.

Is there a divide-and-conquer algorithm for contour tracing of a single blob?

I don't know. Please leave a comment if you find one, because I'd like to learn about that too. I haven't done a serious literature search so I may be ignorant. (Of course you should conceal it if it will form the backbone of your thesis.)

On the other hand, I have implemented a tile-based algorithm for connected-component labeling, based on labeling each tile independently and follow up with a "seam stitching" process, and finish off with a final label assignment. It is not data-parallel (not SIMD/SPMD) but it is highly parallelizable - the image can be divided into hundreds or thousands of tiles.

Regarding performance.

In a previous project where I used contour tracing, I was pleasantly surprised that contour tracing algorithms is in general much faster than the execution time for connected-component labeling algorithms, for the type of images I processed, because contour tracing does not perform as many memory operations as would be required by connected-component labeling.

Note that in general, contour-tracing and connected-component labeling aren't direct substitutes for each other - they give outputs in different representations, despite the outputs corresponding to the same blob. You may have to run both algorithms - label the whole image first, sample the "contour starting points", and trace out the contours of each.

Finding nested connected components.

Smoothing the contour coordinates into floating point.

The smoothing of contour coordinates will cause it to change from discrete (integers) to floating point. After that, you will find that the summation of the pairwise Euclidean distance is good enough for most purposes.

The exact detail of smoothing isn't important - for example, you can use Gaussian smoothing, applying it to the sequence of contour X and Y coordinates just like a 1D convolution. Keep in mind the circular (periodic / wraparound) nature of the sequence.

Source Link
rwong
rwong
  • 17k
  • 3
  • 36
  • 82

I assume that you are not pursuing GPU computation just for the sake of it. In other words, you are willing to consider CPU or "traditional techniques", comparing multiple techniques, and finally choosing whatever gives the highest performance, instead of having to stick to using GPU in order to make a thesis.

I find that Chain Code (contour tracing) algorithm is sufficient for the task, if you smooth the contour coordinates afterwards.

In a previous project where I used contour tracing, I was pleasantly surprised that contour tracing algorithms is in general much faster than connected-component labeling algorithms, for the type of images I processed, because contour tracing does not perform as many memory operations as would be required by connected-component labeling.

There is an enhanced contour tracing algorithm which resolves nested connected component relationship.

  • Given the contour of the outer connected component,
  • Convert the chain code sequence into a sequence of markers.
    • There are two types of markers:
      1. Marks the leftmost edge (begin X-position) of a horizontal run of pixels
      2. Marks the rightmost edge (end X-position) of a horizontal run of pixels
      • Which marker is generated for the current chain code depends on the orientation of the current chain code.
  • Sort the marker sequence by vertical Y-position (major), and then by X-position (minor).
  • The sorted marker sequence then becomes a run-length raster descriptor of the blob surrounded by the contour.

The smoothing of contour coordinates will cause it to change from discrete (integers) to floating point. The exact detail of smoothing isn't important - for example, you can use Gaussian smoothing, applying it to the sequence of contour X and Y coordinates just like a 1D convolution. Keep in mind the circular (periodic / wraparound) nature of the sequence.