{"action":"created","comment":{"url":"https://api.github.com/repos/nipy/dipy/pulls/comments/35760420","id":35760420,"diff_hunk":"@@ -301,3 +301,188 @@ def set_number_of_points(streamlines, nb_points=3):\n         return modified_streamlines[0]\n     else:\n         return modified_streamlines\n+\n+\n+cdef double c_cross_product_normed(double bx, double by, double bz,\n+                                   double cx, double cy, double cz) nogil:\n+    cdef double ax, ay, az\n+    ax = by*cz - bz*cy\n+    ay = bz*cx - bx*cz\n+    az = bx*cy - by*cx\n+    return sqrt(ax*ax + ay*ay + az*az)\n+\n+\n+cdef double c_dist_to_line(Streamline streamline, np.npy_intp prev,\n+                           np.npy_intp next, np.npy_intp curr) nogil:\n+\n+    cdef:\n+        double norm1, norm2\n+        double dn\n+        np.npy_intp D = streamline.shape[1]\n+\n+    # Compute cross product of next-prev and curr-next\n+    norm1 = c_cross_product_normed(streamline[next, 0]-streamline[prev, 0],\n+                                   streamline[next, 1]-streamline[prev, 1],\n+                                   streamline[next, 2]-streamline[prev, 2],\n+                                   streamline[curr, 0]-streamline[next, 0],\n+                                   streamline[curr, 1]-streamline[next, 1],\n+                                   streamline[curr, 2]-streamline[next, 2])\n+\n+    # Norm of next-prev\n+    norm2 = 0.0\n+    for d in range(D):\n+        dn = streamline[next, d]-streamline[prev, d]\n+        norm2 += dn*dn\n+    norm2 = sqrt(norm2)\n+\n+    return norm1 / norm2\n+\n+\n+cdef np.npy_intp c_compress_streamline(Streamline streamline, Streamline out,\n+                                       double tol_error, double max_segment_length) nogil:\n+    cdef:\n+        np.npy_intp N = streamline.shape[0]\n+        np.npy_intp D = streamline.shape[1]\n+        np.npy_intp nb_points = 0\n+        np.npy_intp last_added_point_idx = 0\n+        np.npy_intp last_success = 0\n+        np.npy_intp last_added_point = 0\n+        np.npy_intp i, k, prev, next, curr\n+        double dn, in_between_dist\n+\n+    for i in range(N):\n+        # Euclidean distance between last added point and current point.\n+        in_between_dist = 0.0\n+        for d in range(D):\n+            dn = streamline[i, d] - streamline[last_added_point, d]\n+            in_between_dist += dn*dn\n+\n+        in_between_dist = sqrt(in_between_dist)\n+\n+        if i == 0:  # First point is always added.\n+            for d in range(D):\n+                out[nb_points, d] = streamline[i, d]\n+\n+            last_success = i\n+            nb_points += 1\n+        elif i < N-1:  # Perform linearization if needed.\n+            prev = last_added_point\n+            next = i+1\n+\n+            # Check that each point is not offset by more than `tol_error` mm.\n+            for k in range(last_added_point, i):\n+                curr = k\n+                dist = c_dist_to_line(streamline, prev, next, curr)\n+\n+                # If the current point's offset is greater than `tol_error`, use the latest success.\n+                if dist > tol_error or in_between_dist > max_segment_length:\n+                    for d in range(D):\n+                        out[nb_points, d] = streamline[last_success, d]\n+\n+                    nb_points += 1\n+                    last_added_point = i-1\n+                    last_success = i-1\n+                    break\n+                # The current point's offset is ok, check the next point.\n+                else:\n+                    last_success = i\n+\n+        else:  # Last point is always added.\n+            for d in range(D):\n+                out[nb_points, d] = streamline[i, d]\n+\n+            nb_points += 1\n+\n+    return nb_points\n+\n+\n+def compress_streamlines(streamlines, tol_error=0.1, max_segment_length=10):\n+    \"\"\" Compress streamlines by linearization as in [Presseau15]_.\n+\n+    The compression consists in merging consecutive segments that are\n+    near collinear. The merging is achieved by removing the point the two\n+    segments have in common.\n+\n+    The linearization process [Presseau15]_ ensures that every points being\n+    removed are within a certain margin (in mm) of the resulting streamline.\n+    Recommendations for setting this margin can be found in [Presseau15]_\n+    (in which they called it tolerance error).\n+\n+    The compression also ensures that two consecutive points won't be to far\n+    from each other (precisely less or equal than `max_segment_length`mm).\n+    This is purely to speed up the linearization process [Rheault15]_. A low\n+    value will result in a faster linearization but low compression, whereas\n+    a high value will result in a slower linearization but high compression.\n+\n+    Parameters\n+    ----------\n+    streamlines : one or a list of array-like of shape (N,3)\n+        Array representing x,y,z of N points in a streamline\n+    tol_error : float (optional)\n+        Tolerance error in mm (default: 0.1). A rule of thumb is to set it\n+        to 0.01mm for deterministic streamlines and 0.1mm for probabilitic\n+        streamlines.\n+    max_segment_length : float (optional)\n+        Maximum length of any given segment produced by the compression.","path":"dipy/tracking/streamlinespeed.pyx","position":135,"original_position":135,"commit_id":"8aea6a2f418e5a4e4baccb1a0bfd7057a6eb6120","original_commit_id":"8aea6a2f418e5a4e4baccb1a0bfd7057a6eb6120","user":{"login":"samuelstjean","id":3030760,"avatar_url":"https://avatars.githubusercontent.com/u/3030760?v=3","gravatar_id":"","url":"https://api.github.com/users/samuelstjean","html_url":"https://github.com/samuelstjean","followers_url":"https://api.github.com/users/samuelstjean/followers","following_url":"https://api.github.com/users/samuelstjean/following{/other_user}","gists_url":"https://api.github.com/users/samuelstjean/gists{/gist_id}","starred_url":"https://api.github.com/users/samuelstjean/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/samuelstjean/subscriptions","organizations_url":"https://api.github.com/users/samuelstjean/orgs","repos_url":"https://api.github.com/users/samuelstjean/repos","events_url":"https://api.github.com/users/samuelstjean/events{/privacy}","received_events_url":"https://api.github.com/users/samuelstjean/received_events","type":"User","site_admin":false},"body":"oh wait, that's the max allowed between two points in mm? Then my previous comment is useless. Anyway, you could also add as a note to not do stat on compressed fibers or the result won't be valid at all, just in case people start compressing like crazy and they don't check back changed docstrings.","created_at":"2015-07-29T13:52:41Z","updated_at":"2015-07-29T13:52:41Z","html_url":"https://github.com/nipy/dipy/pull/689#discussion_r35760420","pull_request_url":"https://api.github.com/repos/nipy/dipy/pulls/689","_links":{"self":{"href":"https://api.github.com/repos/nipy/dipy/pulls/comments/35760420"},"html":{"href":"https://github.com/nipy/dipy/pull/689#discussion_r35760420"},"pull_request":{"href":"https://api.github.com/repos/nipy/dipy/pulls/689"}}},"pull_request":{"url":"https://api.github.com/repos/nipy/dipy/pulls/689","id":41019814,"html_url":"https://github.com/nipy/dipy/pull/689","diff_url":"https://github.com/nipy/dipy/pull/689.diff","patch_url":"https://github.com/nipy/dipy/pull/689.patch","issue_url":"https://api.github.com/repos/nipy/dipy/issues/689","number":689,"state":"open","locked":false,"title":"Streamlines compression","user":{"login":"MarcCote","id":660004,"avatar_url":"https://avatars.githubusercontent.com/u/660004?v=3","gravatar_id":"","url":"https://api.github.com/users/MarcCote","html_url":"https://github.com/MarcCote","followers_url":"https://api.github.com/users/MarcCote/followers","following_url":"https://api.github.com/users/MarcCote/following{/other_user}","gists_url":"https://api.github.com/users/MarcCote/gists{/gist_id}","starred_url":"https://api.github.com/users/MarcCote/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MarcCote/subscriptions","organizations_url":"https://api.github.com/users/MarcCote/orgs","repos_url":"https://api.github.com/users/MarcCote/repos","events_url":"https://api.github.com/users/MarcCote/events{/privacy}","received_events_url":"https://api.github.com/users/MarcCote/received_events","type":"User","site_admin":false},"body":"This PR implements the linearization algorithm found in [Presseau et al. *Neuroimage*, 2015](http://scil.dinf.usherbrooke.ca/wp-content/papers/presseau-etal-ni15.pdf).\r\n\r\nBasically, it consists in merging consecutive segments that are near collinear. The merging is achieved by removing the point the two segments share.\r\n\r\nIt can compress 300k streamlines in 10 secs, on a i7-3820 CPU, 3.60GHz. I didn't compare the speed of the C++ version vs. this Cython version, but I will do it and report the speed soon.\r\n@mdesco when you have some time, any comments about the documentation would be appreciated.\r\n\r\nEDIT: I timed the C++ version found in https://github.com/scilus/FiberCompression/ on the same 300k streamlines and it took around 2.5 min. However, this speed down (compare to the Cython version) must be due to the lack of a `max_segment_length` heuristic (see `compress_streamlines` docstring).","created_at":"2015-07-28T14:47:01Z","updated_at":"2015-07-29T13:52:41Z","closed_at":null,"merged_at":null,"merge_commit_sha":"58c95371215204d7aecb24eeca0ef5da41486c95","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/nipy/dipy/pulls/689/commits","review_comments_url":"https://api.github.com/repos/nipy/dipy/pulls/689/comments","review_comment_url":"https://api.github.com/repos/nipy/dipy/pulls/comments{/number}","comments_url":"https://api.github.com/repos/nipy/dipy/issues/689/comments","statuses_url":"https://api.github.com/repos/nipy/dipy/statuses/8aea6a2f418e5a4e4baccb1a0bfd7057a6eb6120","head":{"label":"MarcCote:streamlines_compression","ref":"streamlines_compression","sha":"8aea6a2f418e5a4e4baccb1a0bfd7057a6eb6120","user":{"login":"MarcCote","id":660004,"avatar_url":"https://avatars.githubusercontent.com/u/660004?v=3","gravatar_id":"","url":"https://api.github.com/users/MarcCote","html_url":"https://github.com/MarcCote","followers_url":"https://api.github.com/users/MarcCote/followers","following_url":"https://api.github.com/users/MarcCote/following{/other_user}","gists_url":"https://api.github.com/users/MarcCote/gists{/gist_id}","starred_url":"https://api.github.com/users/MarcCote/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MarcCote/subscriptions","organizations_url":"https://api.github.com/users/MarcCote/orgs","repos_url":"https://api.github.com/users/MarcCote/repos","events_url":"https://api.github.com/users/MarcCote/events{/privacy}","received_events_url":"https://api.github.com/users/MarcCote/received_events","type":"User","site_admin":false},"repo":{"id":8189384,"name":"dipy","full_name":"MarcCote/dipy","owner":{"login":"MarcCote","id":660004,"avatar_url":"https://avatars.githubusercontent.com/u/660004?v=3","gravatar_id":"","url":"https://api.github.com/users/MarcCote","html_url":"https://github.com/MarcCote","followers_url":"https://api.github.com/users/MarcCote/followers","following_url":"https://api.github.com/users/MarcCote/following{/other_user}","gists_url":"https://api.github.com/users/MarcCote/gists{/gist_id}","starred_url":"https://api.github.com/users/MarcCote/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MarcCote/subscriptions","organizations_url":"https://api.github.com/users/MarcCote/orgs","repos_url":"https://api.github.com/users/MarcCote/repos","events_url":"https://api.github.com/users/MarcCote/events{/privacy}","received_events_url":"https://api.github.com/users/MarcCote/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/MarcCote/dipy","description":"Diffusion MR Imaging in Python","fork":true,"url":"https://api.github.com/repos/MarcCote/dipy","forks_url":"https://api.github.com/repos/MarcCote/dipy/forks","keys_url":"https://api.github.com/repos/MarcCote/dipy/keys{/key_id}","collaborators_url":"https://api.github.com/repos/MarcCote/dipy/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/MarcCote/dipy/teams","hooks_url":"https://api.github.com/repos/MarcCote/dipy/hooks","issue_events_url":"https://api.github.com/repos/MarcCote/dipy/issues/events{/number}","events_url":"https://api.github.com/repos/MarcCote/dipy/events","assignees_url":"https://api.github.com/repos/MarcCote/dipy/assignees{/user}","branches_url":"https://api.github.com/repos/MarcCote/dipy/branches{/branch}","tags_url":"https://api.github.com/repos/MarcCote/dipy/tags","blobs_url":"https://api.github.com/repos/MarcCote/dipy/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/MarcCote/dipy/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/MarcCote/dipy/git/refs{/sha}","trees_url":"https://api.github.com/repos/MarcCote/dipy/git/trees{/sha}","statuses_url":"https://api.github.com/repos/MarcCote/dipy/statuses/{sha}","languages_url":"https://api.github.com/repos/MarcCote/dipy/languages","stargazers_url":"https://api.github.com/repos/MarcCote/dipy/stargazers","contributors_url":"https://api.github.com/repos/MarcCote/dipy/contributors","subscribers_url":"https://api.github.com/repos/MarcCote/dipy/subscribers","subscription_url":"https://api.github.com/repos/MarcCote/dipy/subscription","commits_url":"https://api.github.com/repos/MarcCote/dipy/commits{/sha}","git_commits_url":"https://api.github.com/repos/MarcCote/dipy/git/commits{/sha}","comments_url":"https://api.github.com/repos/MarcCote/dipy/comments{/number}","issue_comment_url":"https://api.github.com/repos/MarcCote/dipy/issues/comments{/number}","contents_url":"https://api.github.com/repos/MarcCote/dipy/contents/{+path}","compare_url":"https://api.github.com/repos/MarcCote/dipy/compare/{base}...{head}","merges_url":"https://api.github.com/repos/MarcCote/dipy/merges","archive_url":"https://api.github.com/repos/MarcCote/dipy/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/MarcCote/dipy/downloads","issues_url":"https://api.github.com/repos/MarcCote/dipy/issues{/number}","pulls_url":"https://api.github.com/repos/MarcCote/dipy/pulls{/number}","milestones_url":"https://api.github.com/repos/MarcCote/dipy/milestones{/number}","notifications_url":"https://api.github.com/repos/MarcCote/dipy/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/MarcCote/dipy/labels{/name}","releases_url":"https://api.github.com/repos/MarcCote/dipy/releases{/id}","created_at":"2013-02-13T22:36:58Z","updated_at":"2015-05-08T14:13:31Z","pushed_at":"2015-07-29T02:48:09Z","git_url":"git://github.com/MarcCote/dipy.git","ssh_url":"git@github.com:MarcCote/dipy.git","clone_url":"https://github.com/MarcCote/dipy.git","svn_url":"https://github.com/MarcCote/dipy","homepage":"http://dipy.org","size":16554,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"nipy:master","ref":"master","sha":"647ea4737eca1b276a55eb51fad7ea9756a29ff9","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}","created_at":"2010-02-06T11:43:08Z","updated_at":"2015-07-17T13:52:15Z","pushed_at":"2015-07-29T02:48:10Z","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":30348,"stargazers_count":61,"watchers_count":61,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":95,"mirror_url":null,"open_issues_count":93,"forks":95,"open_issues":93,"watchers":61,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/nipy/dipy/pulls/689"},"html":{"href":"https://github.com/nipy/dipy/pull/689"},"issue":{"href":"https://api.github.com/repos/nipy/dipy/issues/689"},"comments":{"href":"https://api.github.com/repos/nipy/dipy/issues/689/comments"},"review_comments":{"href":"https://api.github.com/repos/nipy/dipy/pulls/689/comments"},"review_comment":{"href":"https://api.github.com/repos/nipy/dipy/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/nipy/dipy/pulls/689/commits"},"statuses":{"href":"https://api.github.com/repos/nipy/dipy/statuses/8aea6a2f418e5a4e4baccb1a0bfd7057a6eb6120"}}}}