{"action":"created","comment":{"url":"https://api.github.com/repos/nipy/dipy/pulls/comments/64996610","id":64996610,"diff_hunk":"@@ -27,17 +28,115 @@ cdef enum:\n     SIJ = 4\n     CNT = 5\n \n+\n @cython.boundscheck(False)\n @cython.wraparound(False)\n @cython.cdivision(True)\n-def precompute_cc_factors_3d(floating[:, :, :] static, floating[:, :, :] moving,\n-                             cnp.npy_intp radius):\n+cdef inline int _wrap(int x, int m)nogil:\n+    r\"\"\" Auxiliary function to `wrap` an array around its low-end side\n+    Negative indices are mapped to last coordinates so that no extra memory\n+    is required to account for local rectangular windows that exceed the\n+    array's low-end boundary.\n+\n+    Parameters\n+    ----------\n+    x : int\n+        the array position to be wrapped\n+    m : int\n+        array length\n+    \"\"\"\n+    if x<0:\n+        return x + m\n+    return x\n+\n+\n+@cython.boundscheck(False)\n+@cython.wraparound(False)\n+@cython.cdivision(True)\n+cdef inline void _update_factors(double[:,:,:,:] factors,\n+                                 floating[:,:,:] moving,\n+                                 floating[:,:,:] static,\n+                                 int ss, int rr, int cc,\n+                                 int s, int r, int c, int operation)nogil:\n+    r\"\"\"Updates the precomputed CC factors of a rectangular window\n+\n+    Updates the precomputed CC factors of the rectangular window centered\n+    at (`ss`, `rr`, `cc`) by adding the factors corresponding to voxel\n+    (`s`, `r`, `c`) of input images `moving` and `static`.\n+\n+    Parameters\n+    ----------\n+    factors : array, shape (S, R, C, 5)\n+        array containing the current precomputed factors to be updated\n+    moving : array, shape (S, R, C)\n+        the moving volume (notice that both images must already be in a common\n+        reference domain, i.e. the same S, R, C)\n+    static : array, shape (S, R, C)\n+        the static volume, which also defines the reference registration domain\n+    ss : int\n+        first coordinate of the rectangular window to be updated\n+    rr : int\n+        second coordinate of the rectangular window to be updated\n+    cc : int\n+        third coordinate of the rectangular window to be updated\n+    s: int\n+        first coordinate of the voxel the local window should be updated with\n+    r: int\n+        second coordinate of the voxel the local window should be updated with\n+    c: int\n+        third coordinate of the voxel the local window should be updated with\n+    operation : int, either -1, 0 or 1\n+        indicates whether the factors of voxel (`s`, `r`, `c`) should be\n+        added to (`operation`=1), subtracted from (`operation`=-1), or set as\n+        (`operation`=0) the current factors for the rectangular window centered\n+        at (`ss`, `rr`, `cc`).\n+\n+    \"\"\"\n+    cdef:\n+        double sval\n+        double mval\n+    if s>=moving.shape[0] or r>=moving.shape[1] or c>=moving.shape[2]:\n+        if operation == 0:\n+            factors[ss, rr, cc, SI] = 0\n+            factors[ss, rr, cc, SI2] = 0\n+            factors[ss, rr, cc, SJ] = 0\n+            factors[ss, rr, cc, SJ2] = 0\n+            factors[ss, rr, cc, SIJ] = 0\n+    else:\n+        sval = static[s,r,c]\n+        mval = moving[s,r,c]\n+        if operation == 0:\n+            factors[ss, rr, cc, SI] = sval\n+            factors[ss, rr, cc, SI2] = sval*sval\n+            factors[ss, rr, cc, SJ] = mval\n+            factors[ss, rr, cc, SJ2] = mval*mval\n+            factors[ss, rr, cc, SIJ] = sval*mval\n+        elif operation == -1:\n+            factors[ss, rr, cc, SI] -= sval\n+            factors[ss, rr, cc, SI2] -= sval*sval\n+            factors[ss, rr, cc, SJ] -= mval\n+            factors[ss, rr, cc, SJ2] -= mval*mval\n+            factors[ss, rr, cc, SIJ] -= sval*mval\n+        elif operation == 1:\n+            factors[ss, rr, cc, SI] += sval\n+            factors[ss, rr, cc, SI2] += sval*sval\n+            factors[ss, rr, cc, SJ] += mval\n+            factors[ss, rr, cc, SJ2] += mval*mval\n+            factors[ss, rr, cc, SIJ] += sval*mval\n+\n+\n+@cython.boundscheck(False)\n+@cython.wraparound(False)\n+@cython.cdivision(True)\n+def precompute_cc_factors_3d(floating[:, :, :] static,\n+                             floating[:, :, :] moving,\n+                             cnp.npy_intp radius, num_threads=None):\n     r\"\"\"Precomputations to quickly compute the gradient of the CC Metric\n \n     Pre-computes the separate terms of the cross correlation metric and image\n     norms at each voxel considering a neighborhood of the given radius to\n     efficiently compute the gradient of the metric with respect to the\n-    deformation field [Avants08][Avants11]\n+    deformation field [Ocegueda16][Avants08][Avants11].","path":"dipy/align/crosscorr.pyx","position":null,"original_position":123,"commit_id":"759d1cc9926b99a5176b652490135e5f8ec904e1","original_commit_id":"2fd50c23ed68d730505d37a2924356c9961f1dc6","user":{"login":"omarocegueda","id":1608583,"avatar_url":"https://avatars.githubusercontent.com/u/1608583?v=3","gravatar_id":"","url":"https://api.github.com/users/omarocegueda","html_url":"https://github.com/omarocegueda","followers_url":"https://api.github.com/users/omarocegueda/followers","following_url":"https://api.github.com/users/omarocegueda/following{/other_user}","gists_url":"https://api.github.com/users/omarocegueda/gists{/gist_id}","starred_url":"https://api.github.com/users/omarocegueda/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/omarocegueda/subscriptions","organizations_url":"https://api.github.com/users/omarocegueda/orgs","repos_url":"https://api.github.com/users/omarocegueda/repos","events_url":"https://api.github.com/users/omarocegueda/events{/privacy}","received_events_url":"https://api.github.com/users/omarocegueda/received_events","type":"User","site_admin":false},"body":"Thanks @arokem!, =)\r\nI just changed the citations in `crosscorr.pyx`. Should I fix the format of all references in the `align` module on this PR, or make a separate one?","created_at":"2016-05-29T01:59:19Z","updated_at":"2016-05-29T01:59:19Z","html_url":"https://github.com/nipy/dipy/pull/1060#discussion_r64996610","pull_request_url":"https://api.github.com/repos/nipy/dipy/pulls/1060","_links":{"self":{"href":"https://api.github.com/repos/nipy/dipy/pulls/comments/64996610"},"html":{"href":"https://github.com/nipy/dipy/pull/1060#discussion_r64996610"},"pull_request":{"href":"https://api.github.com/repos/nipy/dipy/pulls/1060"}}},"pull_request":{"url":"https://api.github.com/repos/nipy/dipy/pulls/1060","id":71587675,"html_url":"https://github.com/nipy/dipy/pull/1060","diff_url":"https://github.com/nipy/dipy/pull/1060.diff","patch_url":"https://github.com/nipy/dipy/pull/1060.patch","issue_url":"https://api.github.com/repos/nipy/dipy/issues/1060","number":1060,"state":"open","locked":false,"title":"Fast computation of Cross Correlation metric","user":{"login":"omarocegueda","id":1608583,"avatar_url":"https://avatars.githubusercontent.com/u/1608583?v=3","gravatar_id":"","url":"https://api.github.com/users/omarocegueda","html_url":"https://github.com/omarocegueda","followers_url":"https://api.github.com/users/omarocegueda/followers","following_url":"https://api.github.com/users/omarocegueda/following{/other_user}","gists_url":"https://api.github.com/users/omarocegueda/gists{/gist_id}","starred_url":"https://api.github.com/users/omarocegueda/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/omarocegueda/subscriptions","organizations_url":"https://api.github.com/users/omarocegueda/orgs","repos_url":"https://api.github.com/users/omarocegueda/repos","events_url":"https://api.github.com/users/omarocegueda/events{/privacy}","received_events_url":"https://api.github.com/users/omarocegueda/received_events","type":"User","site_admin":false},"body":"This PR implements a new algorithm for computing the Cross Correlation metric, which is substantially faster than the original algorithm implemented in ANTS. The computational complexity of the original algorithm for a volume of size N^3 using rectangular windows of size K^3 is Theta(N^3 * K^2). This means that the time increases quadratically with the window radius. \r\n\r\nThe computational complexity of this new algorithm is Theta(N^3), it does not depend on the window size, so we observe a substantial speed up, especially for large rectangular windows. After a conversation with @grlee77, the plan would be to add this algorithm instead of #1051, and then after #1050 is in, we can go ahead and use that framework to parallelize this sequential algorithm to obtain even higher speed up.\r\n\r\nThese are some results on a 4-Core i5-4200H CPU @ 2.80GHz:\r\nOld algorithm, parallel (using #1051):\r\n1 thread\r\n  pre: 1.23728 s\r\n2 threads\r\n  pre: 0.72080 s\r\n4 threads (default)\r\n  pre: 0.69974 s\r\n\r\nNew algorithm (this PR)\r\n1 thread\r\n  pre: 0.15835 s\r\n2 threads\r\n  pre: 0.15837 s\r\n4 threads (default)\r\n  pre: 0.15925 s\r\n(of course it doesn't depend on the number of threads, it's not parallel right now)\r\n\r\nReference: http://www.sciencedirect.com/science/article/pii/S0167865516300861\r\n","created_at":"2016-05-26T16:43:47Z","updated_at":"2016-05-29T01:59:19Z","closed_at":null,"merged_at":null,"merge_commit_sha":"b131937e7dc18f1c23fcd75a4658a70b1aea9bca","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/nipy/dipy/pulls/1060/commits","review_comments_url":"https://api.github.com/repos/nipy/dipy/pulls/1060/comments","review_comment_url":"https://api.github.com/repos/nipy/dipy/pulls/comments{/number}","comments_url":"https://api.github.com/repos/nipy/dipy/issues/1060/comments","statuses_url":"https://api.github.com/repos/nipy/dipy/statuses/759d1cc9926b99a5176b652490135e5f8ec904e1","head":{"label":"omarocegueda:fast_cc","ref":"fast_cc","sha":"759d1cc9926b99a5176b652490135e5f8ec904e1","user":{"login":"omarocegueda","id":1608583,"avatar_url":"https://avatars.githubusercontent.com/u/1608583?v=3","gravatar_id":"","url":"https://api.github.com/users/omarocegueda","html_url":"https://github.com/omarocegueda","followers_url":"https://api.github.com/users/omarocegueda/followers","following_url":"https://api.github.com/users/omarocegueda/following{/other_user}","gists_url":"https://api.github.com/users/omarocegueda/gists{/gist_id}","starred_url":"https://api.github.com/users/omarocegueda/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/omarocegueda/subscriptions","organizations_url":"https://api.github.com/users/omarocegueda/orgs","repos_url":"https://api.github.com/users/omarocegueda/repos","events_url":"https://api.github.com/users/omarocegueda/events{/privacy}","received_events_url":"https://api.github.com/users/omarocegueda/received_events","type":"User","site_admin":false},"repo":{"id":9781072,"name":"dipy","full_name":"omarocegueda/dipy","owner":{"login":"omarocegueda","id":1608583,"avatar_url":"https://avatars.githubusercontent.com/u/1608583?v=3","gravatar_id":"","url":"https://api.github.com/users/omarocegueda","html_url":"https://github.com/omarocegueda","followers_url":"https://api.github.com/users/omarocegueda/followers","following_url":"https://api.github.com/users/omarocegueda/following{/other_user}","gists_url":"https://api.github.com/users/omarocegueda/gists{/gist_id}","starred_url":"https://api.github.com/users/omarocegueda/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/omarocegueda/subscriptions","organizations_url":"https://api.github.com/users/omarocegueda/orgs","repos_url":"https://api.github.com/users/omarocegueda/repos","events_url":"https://api.github.com/users/omarocegueda/events{/privacy}","received_events_url":"https://api.github.com/users/omarocegueda/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/omarocegueda/dipy","description":"Diffusion MR Imaging in Python","fork":true,"url":"https://api.github.com/repos/omarocegueda/dipy","forks_url":"https://api.github.com/repos/omarocegueda/dipy/forks","keys_url":"https://api.github.com/repos/omarocegueda/dipy/keys{/key_id}","collaborators_url":"https://api.github.com/repos/omarocegueda/dipy/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/omarocegueda/dipy/teams","hooks_url":"https://api.github.com/repos/omarocegueda/dipy/hooks","issue_events_url":"https://api.github.com/repos/omarocegueda/dipy/issues/events{/number}","events_url":"https://api.github.com/repos/omarocegueda/dipy/events","assignees_url":"https://api.github.com/repos/omarocegueda/dipy/assignees{/user}","branches_url":"https://api.github.com/repos/omarocegueda/dipy/branches{/branch}","tags_url":"https://api.github.com/repos/omarocegueda/dipy/tags","blobs_url":"https://api.github.com/repos/omarocegueda/dipy/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/omarocegueda/dipy/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/omarocegueda/dipy/git/refs{/sha}","trees_url":"https://api.github.com/repos/omarocegueda/dipy/git/trees{/sha}","statuses_url":"https://api.github.com/repos/omarocegueda/dipy/statuses/{sha}","languages_url":"https://api.github.com/repos/omarocegueda/dipy/languages","stargazers_url":"https://api.github.com/repos/omarocegueda/dipy/stargazers","contributors_url":"https://api.github.com/repos/omarocegueda/dipy/contributors","subscribers_url":"https://api.github.com/repos/omarocegueda/dipy/subscribers","subscription_url":"https://api.github.com/repos/omarocegueda/dipy/subscription","commits_url":"https://api.github.com/repos/omarocegueda/dipy/commits{/sha}","git_commits_url":"https://api.github.com/repos/omarocegueda/dipy/git/commits{/sha}","comments_url":"https://api.github.com/repos/omarocegueda/dipy/comments{/number}","issue_comment_url":"https://api.github.com/repos/omarocegueda/dipy/issues/comments{/number}","contents_url":"https://api.github.com/repos/omarocegueda/dipy/contents/{+path}","compare_url":"https://api.github.com/repos/omarocegueda/dipy/compare/{base}...{head}","merges_url":"https://api.github.com/repos/omarocegueda/dipy/merges","archive_url":"https://api.github.com/repos/omarocegueda/dipy/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/omarocegueda/dipy/downloads","issues_url":"https://api.github.com/repos/omarocegueda/dipy/issues{/number}","pulls_url":"https://api.github.com/repos/omarocegueda/dipy/pulls{/number}","milestones_url":"https://api.github.com/repos/omarocegueda/dipy/milestones{/number}","notifications_url":"https://api.github.com/repos/omarocegueda/dipy/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/omarocegueda/dipy/labels{/name}","releases_url":"https://api.github.com/repos/omarocegueda/dipy/releases{/id}","deployments_url":"https://api.github.com/repos/omarocegueda/dipy/deployments","created_at":"2013-04-30T22:05:45Z","updated_at":"2015-04-21T20:08:08Z","pushed_at":"2016-05-29T01:56:03Z","git_url":"git://github.com/omarocegueda/dipy.git","ssh_url":"git@github.com:omarocegueda/dipy.git","clone_url":"https://github.com/omarocegueda/dipy.git","svn_url":"https://github.com/omarocegueda/dipy","homepage":"http://dipy.org","size":21792,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":2,"forks":0,"open_issues":2,"watchers":0,"default_branch":"master"}},"base":{"label":"nipy:master","ref":"master","sha":"9a9a4ecfae9c2717cf7c2b666e46c0a9e3994634","user":{"login":"nipy","id":233707,"avatar_url":"https://avatars.githubusercontent.com/u/233707?v=3","gravatar_id":"","url":"https://api.github.com/users/nipy","html_url":"https://github.com/nipy","followers_url":"https://api.github.com/users/nipy/followers","following_url":"https://api.github.com/users/nipy/following{/other_user}","gists_url":"https://api.github.com/users/nipy/gists{/gist_id}","starred_url":"https://api.github.com/users/nipy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nipy/subscriptions","organizations_url":"https://api.github.com/users/nipy/orgs","repos_url":"https://api.github.com/users/nipy/repos","events_url":"https://api.github.com/users/nipy/events{/privacy}","received_events_url":"https://api.github.com/users/nipy/received_events","type":"Organization","site_admin":false},"repo":{"id":505209,"name":"dipy","full_name":"nipy/dipy","owner":{"login":"nipy","id":233707,"avatar_url":"https://avatars.githubusercontent.com/u/233707?v=3","gravatar_id":"","url":"https://api.github.com/users/nipy","html_url":"https://github.com/nipy","followers_url":"https://api.github.com/users/nipy/followers","following_url":"https://api.github.com/users/nipy/following{/other_user}","gists_url":"https://api.github.com/users/nipy/gists{/gist_id}","starred_url":"https://api.github.com/users/nipy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nipy/subscriptions","organizations_url":"https://api.github.com/users/nipy/orgs","repos_url":"https://api.github.com/users/nipy/repos","events_url":"https://api.github.com/users/nipy/events{/privacy}","received_events_url":"https://api.github.com/users/nipy/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/nipy/dipy","description":"Diffusion MR Imaging in Python","fork":false,"url":"https://api.github.com/repos/nipy/dipy","forks_url":"https://api.github.com/repos/nipy/dipy/forks","keys_url":"https://api.github.com/repos/nipy/dipy/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nipy/dipy/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nipy/dipy/teams","hooks_url":"https://api.github.com/repos/nipy/dipy/hooks","issue_events_url":"https://api.github.com/repos/nipy/dipy/issues/events{/number}","events_url":"https://api.github.com/repos/nipy/dipy/events","assignees_url":"https://api.github.com/repos/nipy/dipy/assignees{/user}","branches_url":"https://api.github.com/repos/nipy/dipy/branches{/branch}","tags_url":"https://api.github.com/repos/nipy/dipy/tags","blobs_url":"https://api.github.com/repos/nipy/dipy/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nipy/dipy/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nipy/dipy/git/refs{/sha}","trees_url":"https://api.github.com/repos/nipy/dipy/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nipy/dipy/statuses/{sha}","languages_url":"https://api.github.com/repos/nipy/dipy/languages","stargazers_url":"https://api.github.com/repos/nipy/dipy/stargazers","contributors_url":"https://api.github.com/repos/nipy/dipy/contributors","subscribers_url":"https://api.github.com/repos/nipy/dipy/subscribers","subscription_url":"https://api.github.com/repos/nipy/dipy/subscription","commits_url":"https://api.github.com/repos/nipy/dipy/commits{/sha}","git_commits_url":"https://api.github.com/repos/nipy/dipy/git/commits{/sha}","comments_url":"https://api.github.com/repos/nipy/dipy/comments{/number}","issue_comment_url":"https://api.github.com/repos/nipy/dipy/issues/comments{/number}","contents_url":"https://api.github.com/repos/nipy/dipy/contents/{+path}","compare_url":"https://api.github.com/repos/nipy/dipy/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nipy/dipy/merges","archive_url":"https://api.github.com/repos/nipy/dipy/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nipy/dipy/downloads","issues_url":"https://api.github.com/repos/nipy/dipy/issues{/number}","pulls_url":"https://api.github.com/repos/nipy/dipy/pulls{/number}","milestones_url":"https://api.github.com/repos/nipy/dipy/milestones{/number}","notifications_url":"https://api.github.com/repos/nipy/dipy/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nipy/dipy/labels{/name}","releases_url":"https://api.github.com/repos/nipy/dipy/releases{/id}","deployments_url":"https://api.github.com/repos/nipy/dipy/deployments","created_at":"2010-02-06T11:43:08Z","updated_at":"2016-04-25T18:11:15Z","pushed_at":"2016-05-29T01:56:03Z","git_url":"git://github.com/nipy/dipy.git","ssh_url":"git@github.com:nipy/dipy.git","clone_url":"https://github.com/nipy/dipy.git","svn_url":"https://github.com/nipy/dipy","homepage":"http://dipy.org","size":40585,"stargazers_count":89,"watchers_count":89,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":132,"mirror_url":null,"open_issues_count":149,"forks":132,"open_issues":149,"watchers":89,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/nipy/dipy/pulls/1060"},"html":{"href":"https://github.com/nipy/dipy/pull/1060"},"issue":{"href":"https://api.github.com/repos/nipy/dipy/issues/1060"},"comments":{"href":"https://api.github.com/repos/nipy/dipy/issues/1060/comments"},"review_comments":{"href":"https://api.github.com/repos/nipy/dipy/pulls/1060/comments"},"review_comment":{"href":"https://api.github.com/repos/nipy/dipy/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/nipy/dipy/pulls/1060/commits"},"statuses":{"href":"https://api.github.com/repos/nipy/dipy/statuses/759d1cc9926b99a5176b652490135e5f8ec904e1"}}}}
{"actor":{"display_login":"omarocegueda"}}