In this paper, a two stage co-segmentation method,based on matrix decomposition,has been proposed. In the first step, each image is segmented into some super-pixels and then salient parts of each image are extracted via structured matrix decomposition (SMD) method. The low-rank matrix represents image background and the sparse matrix contains salient objects. In this step, the super-pixels that are partitioned as background with high confidence will be removed. In the second step, all remaining super-pixels are considered all together and the tree structure is rearranged and then the SMD method is applied again to this new data. Parts of the common salient object compose the low-rank matrix due to the large number of them in the remaining super-pixels. In other words, the proposed approach has embedded intra-image adjacency information and inter-images similarity information into the matrix decomposition method via proper weighting of the tree structure.iCoseg dataset has been used to evaluate its performance. The results demonstrate its effectiveness and superiority.