Databases
StackOverflow2013
Postsdbo
POMemory-efficient line stitching in very large images
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMemory-efficient line stitching in very large images
    primarykey
    data
    text
    <h2>Background</h2> <p>I work with very large datasets from Synthetic Aperture Radar satellites. These can be thought of as high dynamic range greyscale images of the order of 10k pixels on a side.</p> <p>Recently, I've been developing applications of a single-scale variant of <a href="http://www.springerlink.com/content/u624470167857570/" rel="nofollow noreferrer">Lindeberg's scale-space ridge detection algorithm method</a> for detecting linear features in a SAR image. This is an improvement on using directional filters or using the Hough Transform, methods that have both previously been used, because it is less computationally expensive than either. (I will be presenting some recent results at <a href="http://www.pf.bv.tum.de/jurse2011/index.html" rel="nofollow noreferrer">JURSE 2011</a> in April, and I can upload a preprint if that would be helpful).</p> <p>The code I currently use generates an array of records, one per pixel, each of which describes a ridge segment in the rectangle to bottom right of the pixel and bounded by adjacent pixels.</p> <pre><code>struct ridge_t { unsigned char top, left, bottom, right }; int rows, cols; struct ridge_t *ridges; /* An array of rows*cols ridge entries */ </code></pre> <p>An entry in <code>ridges</code> contains a ridge segment if exactly two of <code>top</code>, <code>left</code>, <code>right</code> and <code>bottom</code> have values in the range 0 - 128. Suppose I have:</p> <pre><code>ridge_t entry; entry.top = 25; entry.left = 255; entry.bottom = 255; entry.right = 76; </code></pre> <p>Then I can find the ridge segment's start (x1,y1) and end (x2,y2):</p> <pre><code>float x1, y1, x2, y2; x1 = (float) col + (float) entry.top / 128.0; y1 = (float) row; x2 = (float) col + 1; y2 = (float) row + (float) entry.right / 128.0; </code></pre> <p>When these individual ridge segments are rendered, I get an image something like this (a very small corner of a far larger image):</p> <p><img src="https://i.stack.imgur.com/pBRRK.png" alt="Rendered ridge segments"></p> <p>Each of those long curves are rendered from a series of tiny ridge segments.</p> <p>It's trivial to determine whether two adjacent locations which contain ridge segments are connected. If I have <code>ridge1</code> at (x, y) and <code>ridge2</code> at (x+1, y), then they are parts of the same line if 0 &lt;= <code>ridge1.right</code> &lt;= 128 <em>and</em> <code>ridge2.left</code> = <code>ridge1.right</code>.</p> <h2>Problem</h2> <p>Ideally, I would like to stitch together all of the ridge segments into lines, so that I can then iterate over each <em>line</em> found in the image to apply further computations. Unfortunately, I'm finding it hard to find an algorithm for doing this which is both low complexity <em>and</em> memory-efficient <em>and</em> suitable for multiprocessing (all important consideration when dealing with really huge images!)</p> <p>One approach that I have considered is scanning through the image until I find a ridge which only has one linked ridge segment, and then walking the resulting line, flagging any ridges in the line as visited. However, this is unsuitable for multiprocessing, because there's no way to tell if there isn't another thread walking the same line from the other direction (say) without expensive locking.</p> <p>What do readers suggest as a possible approach? It seems like the sort of thing that someone would have figured out an efficient way to do in the past...</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USPeter T.B. Brett
    1. USPeter T.B. Brett
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POMemory-efficient line stitching in very large images
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POMemory-efficient line stitching in very large images
      1. USbdonlan
      1. VTFavorite
    3. VO
      singulars
      1. POMemory-efficient line stitching in very large images
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1 for such a well written question.
      singulars
      1. POMemory-efficient line stitching in very large images
      1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload