1 | % * This code was used in the following articles:
|
---|
2 | % * [1] Learning 3-D Scene Structure from a Single Still Image,
|
---|
3 | % * Ashutosh Saxena, Min Sun, Andrew Y. Ng,
|
---|
4 | % * In ICCV workshop on 3D Representation for Recognition (3dRR-07), 2007.
|
---|
5 | % * (best paper)
|
---|
6 | % * [2] 3-D Reconstruction from Sparse Views using Monocular Vision,
|
---|
7 | % * Ashutosh Saxena, Min Sun, Andrew Y. Ng,
|
---|
8 | % * In ICCV workshop on Virtual Representations and Modeling
|
---|
9 | % * of Large-scale environments (VRML), 2007.
|
---|
10 | % * [3] 3-D Depth Reconstruction from a Single Still Image,
|
---|
11 | % * Ashutosh Saxena, Sung H. Chung, Andrew Y. Ng.
|
---|
12 | % * International Journal of Computer Vision (IJCV), Aug 2007.
|
---|
13 | % * [6] Learning Depth from Single Monocular Images,
|
---|
14 | % * Ashutosh Saxena, Sung H. Chung, Andrew Y. Ng.
|
---|
15 | % * In Neural Information Processing Systems (NIPS) 18, 2005.
|
---|
16 | % *
|
---|
17 | % * These articles are available at:
|
---|
18 | % * http://make3d.stanford.edu/publications
|
---|
19 | % *
|
---|
20 | % * We request that you cite the papers [1], [3] and [6] in any of
|
---|
21 | % * your reports that uses this code.
|
---|
22 | % * Further, if you use the code in image3dstiching/ (multiple image version),
|
---|
23 | % * then please cite [2].
|
---|
24 | % *
|
---|
25 | % * If you use the code in third_party/, then PLEASE CITE and follow the
|
---|
26 | % * LICENSE OF THE CORRESPONDING THIRD PARTY CODE.
|
---|
27 | % *
|
---|
28 | % * Finally, this code is for non-commercial use only. For further
|
---|
29 | % * information and to obtain a copy of the license, see
|
---|
30 | % *
|
---|
31 | % * http://make3d.stanford.edu/publications/code
|
---|
32 | % *
|
---|
33 | % * Also, the software distributed under the License is distributed on an
|
---|
34 | % * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
|
---|
35 | % * express or implied. See the License for the specific language governing
|
---|
36 | % * permissions and limitations under the License.
|
---|
37 | % *
|
---|
38 | % */
|
---|
39 | % performs Min Cut
|
---|
40 | % input - list of vertices to keep togeather and weighted CLICK !!! <=====
|
---|
41 | % output -
|
---|
42 | % MinCutGroupsList - two lists of verices, SECOND one contains the sourve vertives
|
---|
43 | % MinCutWeight - weight on cut
|
---|
44 | function [MinCutGroupsList, MinCutWeight] = MinCut(SourceVertices, WeightedGraph)
|
---|
45 |
|
---|
46 | GraphDim = size(WeightedGraph,1);
|
---|
47 | SourceVertices = SourceVertices(find(SourceVertices));
|
---|
48 |
|
---|
49 | % remove self edges and ZEROed ones
|
---|
50 | for ii = 1:GraphDim
|
---|
51 | WeightedGraph(ii,ii) = inf;
|
---|
52 | end
|
---|
53 | WeightedGraph(find(WeightedGraph == 0)) = inf;
|
---|
54 |
|
---|
55 | %Merge all Source Vrtices to one, so they'll be unbreakable, descending order is VITAL!!!
|
---|
56 | SourceVertices = sort(SourceVertices);
|
---|
57 | GroupsList = zeros(GraphDim); %each row are the vertices melted into one vertex in the table.
|
---|
58 | GroupsList(:,1) = 1:GraphDim;
|
---|
59 | for ii=length(SourceVertices):-1:2;
|
---|
60 | [WeightedGraph,GroupsList] = MeltTwoVertices(SourceVertices(1),SourceVertices(ii),WeightedGraph,GroupsList);
|
---|
61 | end
|
---|
62 | Split = GroupsList(:,1);
|
---|
63 |
|
---|
64 | [MinCutGroupsList_L, MinCutWeight] = MinCutNoSeed(WeightedGraph);
|
---|
65 | for ii = 1:2
|
---|
66 | MinCutGroupsList(ii,:) = Local2GlobalIndices(MinCutGroupsList_L(ii,:), Split);
|
---|
67 | end
|
---|
68 |
|
---|
69 | if (length(find(MinCutGroupsList(1,:) == SourceVertices(1))) == 1)
|
---|
70 | SeedLocation = 1;
|
---|
71 | else
|
---|
72 | SeedLocation = 2;
|
---|
73 | end
|
---|
74 | MinCutGroupsList_withSeed = [MinCutGroupsList(SeedLocation,find(MinCutGroupsList(SeedLocation,:))) SourceVertices(2:length(SourceVertices))];
|
---|
75 | MinCutGroupsList_withSeed = sort(MinCutGroupsList_withSeed);
|
---|
76 | MinCutGroupsList_withSeed = [MinCutGroupsList_withSeed zeros(1,GraphDim - length(MinCutGroupsList_withSeed))];
|
---|
77 |
|
---|
78 | MinCutGroupsList_NoSeed = MinCutGroupsList(3 - SeedLocation,find(MinCutGroupsList(3 - SeedLocation,:)));
|
---|
79 | MinCutGroupsList_NoSeed = sort(MinCutGroupsList_NoSeed);
|
---|
80 | MinCutGroupsList_NoSeed = [MinCutGroupsList_NoSeed zeros(1,GraphDim - length(MinCutGroupsList_NoSeed))];
|
---|
81 |
|
---|
82 | MinCutGroupsList = [MinCutGroupsList_NoSeed ; MinCutGroupsList_withSeed];
|
---|
83 |
|
---|
84 |
|
---|
85 |
|
---|
86 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
|
---|
87 | function [MinCutGroupsList, MinCutWeight] = MinCutNoSeed(WeightedGraph)
|
---|
88 | GraphDim = size(WeightedGraph,1);
|
---|
89 | GroupsList = zeros(GraphDim);
|
---|
90 | GroupsList(:,1) = 1:GraphDim;
|
---|
91 |
|
---|
92 | MinCutWeight = inf;
|
---|
93 | MinCutGroup = [];
|
---|
94 | for ii = 1:GraphDim-1
|
---|
95 | [OneBefore, LastVertex] = MinimumCutPhase(WeightedGraph);
|
---|
96 | if OneBefore == -1 %Graph is not connected. LastVertex is a group of vertices not connected to Vertex 1
|
---|
97 | MinCutGroup_L = LastVertex(find(LastVertex)); clear LastVertex; %it's not the last vertex
|
---|
98 |
|
---|
99 | MinCutGroupsList = [];
|
---|
100 | for jj = 1:length(MinCutGroup_L);
|
---|
101 | MinCutGroup_temp = GroupsList(MinCutGroup_L(jj));
|
---|
102 | MinCutGroup_temp = MinCutGroup_temp(find(MinCutGroup_temp));
|
---|
103 | MinCutGroupsList = [MinCutGroupsList MinCutGroup_temp];
|
---|
104 | end
|
---|
105 | MinCutGroupsList = [MinCutGroupsList zeros(1,GraphDim - length(MinCutGroupsList))];
|
---|
106 |
|
---|
107 | jj = 1;
|
---|
108 | for kk=1:GraphDim
|
---|
109 | if length(find(MinCutGroupsList(1,:) == kk)) == 0
|
---|
110 | MinCutGroupsList(2 ,jj) = kk;
|
---|
111 | jj = jj + 1;
|
---|
112 | end
|
---|
113 | end
|
---|
114 | MinCutWeight = 0;
|
---|
115 | return
|
---|
116 | end %of: If graph is not connected
|
---|
117 | Edges = WeightedGraph(LastVertex,:);
|
---|
118 | Edges = Edges(isfinite(Edges));
|
---|
119 | MinCutPhaseWeight = sum(Edges);
|
---|
120 | if MinCutPhaseWeight < MinCutWeight
|
---|
121 | MinCutWeight = MinCutPhaseWeight;
|
---|
122 | MinCutGroup = GroupsList(LastVertex,:);
|
---|
123 | MinCutGroup = MinCutGroup(find(MinCutGroup));
|
---|
124 | end
|
---|
125 | [WeightedGraph,GroupsList] = MeltTwoVertices(LastVertex,OneBefore,WeightedGraph,GroupsList);
|
---|
126 | end
|
---|
127 |
|
---|
128 | MinCutGroup = sort(MinCutGroup);
|
---|
129 | MinCutGroupsList = [MinCutGroup zeros(1,GraphDim - length(MinCutGroup))];
|
---|
130 |
|
---|
131 | jj = 1;
|
---|
132 | for kk=1:GraphDim
|
---|
133 | if length(find(MinCutGroup(1,:) == kk)) == 0
|
---|
134 | MinCutGroupsList(2 ,jj) = kk;
|
---|
135 | jj = jj + 1;
|
---|
136 | end
|
---|
137 | end
|
---|
138 |
|
---|
139 | % This function takes V1 and V2 as vertexes in the given graph and MERGES
|
---|
140 | % THEM INTO V1 !!
|
---|
141 | function [UpdatedGraph,GroupsList] = MeltTwoVertices(V1,V2,WeightedGraph,GroupsList)
|
---|
142 | t = min(V1,V2);
|
---|
143 | V2 = max(V1,V2);
|
---|
144 | V1 = t;
|
---|
145 |
|
---|
146 | GraphDim = size(WeightedGraph,1);
|
---|
147 | UpdatedGraph = WeightedGraph;
|
---|
148 |
|
---|
149 | Mask1 = isinf(WeightedGraph(V1,:) );
|
---|
150 | Mask2 = isinf(WeightedGraph(V2,:) );
|
---|
151 | UpdatedGraph(V1,Mask1) = 0;
|
---|
152 | UpdatedGraph(V2,Mask2) = 0;
|
---|
153 | infMask = zeros(1,size(Mask1,2));
|
---|
154 | infMask(find(Mask1 & Mask2)) = inf;
|
---|
155 | UpdatedGraph(V1,:) = UpdatedGraph(V1,:) + UpdatedGraph(V2,:) + infMask;
|
---|
156 | UpdatedGraph(:,V1) = UpdatedGraph(V1,:)';
|
---|
157 | UpdatedGraph = [UpdatedGraph(1:V2-1,:) ; UpdatedGraph(V2+1:GraphDim,:)]; %remove second vertex from graph
|
---|
158 | UpdatedGraph = [UpdatedGraph(:,1:V2-1) UpdatedGraph(:,V2+1:GraphDim)];
|
---|
159 | UpdatedGraph(V1,V1) = inf; % group-group distance
|
---|
160 |
|
---|
161 | V1list = GroupsList(V1,find( GroupsList(V1,:) ) );
|
---|
162 | V2list = GroupsList(V2,find( GroupsList(V2,:) ) );
|
---|
163 | GroupsList(V1,:) = [V1list V2list zeros(1,size( GroupsList,2)- length(V1list) - length(V2list)) ]; %shorten grouplist
|
---|
164 | GroupsList = [GroupsList(1:V2-1,:) ;GroupsList(V2+1:GraphDim,:) ];
|
---|
165 |
|
---|
166 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
---|
167 | % return [-1, B ] in case of Unconnected Graph when B is a subgraph(s)
|
---|
168 | % that are not connected to Vertex 1
|
---|
169 | function [OneBefore, LastVertex] = MinimumCutPhase(WeightedGraph)
|
---|
170 | GraphDim = size(WeightedGraph,1);
|
---|
171 | GroupsList = zeros(GraphDim);
|
---|
172 | GroupsList(:,1) = 1:GraphDim;
|
---|
173 |
|
---|
174 | if size(WeightedGraph,1) > 2
|
---|
175 | FarestVertexGroup = [0];
|
---|
176 | for ii = 1:GraphDim-1
|
---|
177 | OneBefore = FarestVertexGroup(1);
|
---|
178 | PossibleVertices = WeightedGraph(1,1:size(WeightedGraph,2));
|
---|
179 | PossibleVertices(isinf(PossibleVertices)) = 0;
|
---|
180 | FarestVertex = min(find(PossibleVertices == max(PossibleVertices)));
|
---|
181 | if FarestVertex == 1 %In case the Graph is not connected
|
---|
182 | OneBefore = -1;
|
---|
183 | LastVertex = GroupsList(1,:);
|
---|
184 | return
|
---|
185 | end
|
---|
186 | FarestVertexGroup = GroupsList(FarestVertex,:);
|
---|
187 | [WeightedGraph,GroupsList] = MeltTwoVertices(1,FarestVertex,WeightedGraph,GroupsList);
|
---|
188 | end
|
---|
189 | LastVertex = FarestVertexGroup(1);
|
---|
190 | else
|
---|
191 | OneBefore = 1;
|
---|
192 | LastVertex = 2;
|
---|
193 | end |
---|