Databases
StackOverflow2013
Postsdbo
POSpeeding up self-similarity in an image
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSpeeding up self-similarity in an image
    text
    copied!<p>I'm writing a program that will generate images. One measurement that I want is the amount of "self-similarity" in the image. I wrote the following code that looks for the countBest-th best matches for each sizeWindow * sizeWindow window in the picture:</p> <pre><code>double Pattern::selfSimilar(int sizeWindow, int countBest) { std::vector&lt;int&gt; *pvecount; double similarity; int match; int x1; int x2; int xWindow; int y1; int y2; int yWindow; similarity = 0.0; // (x1, y1) is the original that's looking for matches. for (x1 = 0; x1 &lt; k_maxX - sizeWindow; x1++) { for (y1 = 0; y1 &lt; k_maxY - sizeWindow; y1++) { pvecount = new std::vector&lt;int&gt;(); // (x2, y2) is the possible match. for (x2 = 0; x2 &lt; k_maxX - sizeWindow; x2++) { for (y2 = 0; y2 &lt; k_maxY - sizeWindow; y2++) { // Testing... match = 0; for (xWindow = 0; xWindow &lt; sizeWindow; xWindow++) { for (yWindow = 0; yWindow &lt; sizeWindow; yWindow++) { if (m_color[x1 + xWindow][y1 + yWindow] == m_color[x2 + xWindow][y2 + yWindow]) { match++; } } } pvecount-&gt;push_back(match); } } nth_element(pvecount-&gt;begin(), pvecount-&gt;end()-countBest, pvecount-&gt;end()); similarity += (1.0 / ((k_maxX - sizeWindow) * (k_maxY - sizeWindow))) * (*(pvecount-&gt;end()-countBest) / (double) (sizeWindow * sizeWindow)); delete pvecount; } } return similarity; } </code></pre> <p>The good news is that the algorithm does what I want it to: it will return a value from 0.0 to 1.0 about how 'self-similar' a picture is.</p> <p>The bad news -- as I'm sure that you've already noted -- is that the algorithm is extremely slow. It takes <code>(k_maxX - sizeWindow) * (k_maxY - sizeWindow) * (k_maxX - sizeWindow) * (k_maxY - sizeWindow) * sizeWindow * sizeWindow</code> steps for a run. </p> <p>Some typical values for the variables:</p> <pre><code>k_maxX = 1280 k_maxY = 1024 sizeWindow = between 5 and 25 countBest = 3, 4, or 5 m_color[x][y] is defined as short m_color[k_maxX][k_maxY] with values between 0 and 3 (but may increase in the future.) </code></pre> <p>Right now, I'm <strong>not</strong> worried about the memory footprint taken by pvecount. Later, I can use a sorted data set that doesn't add another element when it's smaller than countBest. I am only worried about algorithm speed.</p> <p>How can I speed this up?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

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