如何在三维域中检测某序列的结束位置（x，y，z）

Question

我对蛋白质进行了三维creo-EM扫描，这样它就包含了一条围绕自身弯曲和扭曲的链，并且在三维空间中有两条链的末端（就像连续的绳子）。我需要检测（x，y，z）的位置在给定的立方体空间的两个或可能的乘数2结束。扫描的立方体空间由扫描电镜提供的每个体素的密度表示（范围从0到1），因此“现有物质”给出的值接近1，“无物质”给出的密度值接近0。我需要一种方法来检测蛋白质的“绳子”边缘（可能的“绳子结束”的定义是在某些缠结的方向缺乏连续性。直观地说，我认为至少有两种方法：1）图论中的某个方法（我不能精确地指定-如果你知道一个-请命名或描述它）。2） 解析代数的导数-但我又不能说明具体的态度-所以请说出或解释一个。请指定建议方法的计算复杂度。我的项目是用Python实现的。请帮忙。提前谢谢。你知道吗

Answer 1

一种方法是选择阈值密度，将低于该阈值的所有体素转换为0，将高于该阈值的所有体素转换为1，然后在所有1-体素对中查找最短路径最长的1-体素对。这两个体素应该靠近最长的“绳子”的末端，而不管绳子的确切形状如何。你知道吗

可以定义一个图，其中每个1体素有一个顶点，每个1体素与其6个（或可能14个）相邻体之间有一条边。然后，可以使用广度优先搜索（这里不需要Dijkstra或Floyd Warshall，因为每条边都有权1），计算某个给定顶点u和O（| V |）时间和空间中其他每个顶点之间的最短路径的长度。对每个可能的起始顶点u重复此操作将给出一个O（| V | ^2）-时间算法。当你这么做的时候，要追踪到目前为止最远的一对。你知道吗

如果你的体素空间有w*h*d个单元，那么图中可能有w*h*d个顶点（如果每个体素都是1个体素），所以在最坏的情况下这可能需要O（w^2*h^2*d^2）时间，这可能是相当多的。幸运的是，如果你能负担得起一个稍微不精确的答案，有很多方法可以加快速度：

• 仅从边界处的起始顶点计算最短路径，即具有少于6个（或14个）邻居的顶点。（我相信这不会牺牲最佳解决方案。）
• 或者，首先“骨架化”的图形，通过反复摆脱所有这样的边界顶点删除不会断开图形。你知道吗
• 选择起始顶点的一个好方法是首先选择任何顶点，然后始终选择一个与最后一个顶点的最大可能距离的顶点（当然还没有尝试过）。这将使您在3次迭代后获得一个非常好的最长-最短路径的近似值：距起始顶点最远的顶点将靠近两个绳索末端之一，距该顶点最远的顶点将靠近另一端！你知道吗

注意：如果由于弯曲，绳子上彼此靠近的远点之间没有完整的体素间隙，那么最短路径将通过这些错误连接“短路”，并可能降低精确度。您可以通过增加阈值来改善这一点。如果门槛太高，绳子就会断开。我希望您希望选择仅导致1个连接组件的最高阈值。你知道吗

Answer 2

如果要在三维扫描中枚举每个连续路径（从而获得每个路径的端点），可以对每个位置应用基本的深度优先搜索，例如：

//applied at some voxel
dfs(...)
    for each surrounding voxel 
        dfs(...)

或细节：

class coordinate{
    x
    y
    z
    visited
}

initialize pathList
initialize coords

add all coordinates which contain "matter" to coords

dfs(coordinate,path)
    coordinate.visited = TRUE
    isEnd = TRUE
    FOR each coordinate
        //check each of the 26 possible locations (total 26 conditionals)
        IF coordinate.get(x-1,y-1,z+1) IN coords AND 
           NOT coordinate.get(x-1,y-1,z+1).visited THEN
            isEnd = FALSE
            path += coordinate.get(x-1,y-1,z+1)
            dfs(coordinate.get(x-1,y-1,z+1),path)
        ...
        IF coordinate.get(x+1,y+1,z-1) IN coords AND 
           NOT coordinate.get(x+1,y+1,z-1).visited THEN 
            isEnd = FALSE
            path += coordinate.get(x+1,y+1,z-1) 
            dfs(coordinate.get(x+1,y+1,z-1),path)
    IF isEnd THEN
        add path to pathList
    remove coordinate from coords

WHILE coords isn't empty
    dfs(coords.get(0),"")

通用过程（dfs）在许多其他站点上都有很好的文档记录，但是如果您想测试它，这里有一些粗糙的java（我对python不太熟悉）可以反映上面的内容：

public class C {

    ArrayList<Coordinate> coords = new ArrayList<>();
    ArrayList<String> paths = new ArrayList<>();



    static class Coordinate {
        int x, y, z;
        boolean visited;
        Coordinate(int x,int y,int z){
            this.x = x;
            this.y = y;
            this.z = z;
            visited = false;
        }

        public String toString() {
            return "("+x+","+y+","+z+")";
        }
    }



    void dfs(Coordinate c,String path) {
        c.visited=true;
        path+=c.toString();
        boolean isEnd = true;
        //apply dfs to 26 possible neighbors
        for(int x = c.x-1; x <= c.x+1; x++) {
            for (int y = c.y-1; y <= c.y+1; y++) {
                for (int z = c.z+1; z >= c.z-1; z ) {
                    Coordinate coord = getCoordinate(x,y,z);
                    //if coord exists and it's not been visited
                    if(coord!=null && !coord.visited && !coord.equals(c)) {
                        isEnd = false;
                        dfs(coord, path);
                    }
                }
            }
        }
        if(isEnd) paths.add(path);

        coords.remove(c);
    }

    Coordinate getCoordinate(int x,int y,int z){
        for(Coordinate b: coords){
            if(x==b.x && y==b.y && z==b.z) return b;
        }
        return null;
    }


    void search(){
        //while there are points in 3d space extend a path from one
        while(!coords.isEmpty()){
            dfs(coords.get(0),"");
        }
    }




    public static void main(String[] args) {

        C coord = new C();

        //for each place where there exists matter
        //create a coordinate object and add to coords
        // for example:
        coord.coords.add(new Coordinate(0,0,0));
        coord.coords.add(new Coordinate(-1,1,1));
        coord.coords.add(new Coordinate(1,1,1));
        coord.coords.add(new Coordinate(-1,2,2));
        coord.coords.add(new Coordinate(-1,0,2));
        coord.coords.add(new Coordinate(1,2,2));
        coord.coords.add(new Coordinate(1,0,2));

        coord.search();
        //print out each path on separate line, 
        //the path endings can easily be obtained from this 
        for(String s:coord.paths) System.out.println(s);

    }
}