[37] | 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 |
---|