8.5 Segmentation by Split and Merge Techniques

Chapter Contents (Back)
Split and Merge. Segmentation, Split and Merge. Segmentation, Region Merging. Segmentation, Region Splitting. Quadtree.

Horowitz, S.L., and Pavlidis, T.,
Picture Segmentation by a Tree Traversal Algorithm,
JACM(23), No. 2, April 1976, pp. 368-388. Segmentation, Split and Merge. The standard split and merge basic reference. The basics are, split the image into regular shapes (quarters), if it is non-uniform recursively split the subimages. When no more splits, merge adjacent similar subimages, and merge those remaining that are too small. BibRef 7604

Horowitz, S.L., and Pavlidis, T.,
Picture Segmentation by a Directed Split and Merge Procedure,
ICPR74(424-433). BibRef 7400 CMetImAly77(101-11). Good early reference to the method. BibRef

Horowitz, S.L., and Pavlidis, T.,
A Graph-Theoretic Approach to Picture Processing,
CGIP(7), No. 2, April 1978, pp. 282-291.
WWW Version. BibRef 7804
Earlier:
Picture Processing by Graph Analysis,
CGPR75(125-129). BibRef

Tanimoto, S.L., and Pavlidis, T.,
The Editing of Picture Segmentations Using Local Analysis of Graphs,
CACM(20), No. 4, April 1977, pp. 223-229. BibRef 7704

Pavlidis, T., Tanimoto, S.L.,
Texture Identification by a Directed Split-and Merge Procedure,
CGPR75(201-203). BibRef 7500

Gupta, J.N., and Wintz, P.A.,
A Boundary Finding Algorithm and Its Applications,
CirSys(22), No. 4, April 1975, pp. 351-362. Segmentation, Texture. Merging on texture, use one or both of first or second order statistics. BibRef 7504

Lemkin, P.,
An Approach to Region Splitting,
CGIP(10), No. 3, July 1979, pp. 281-288.
WWW Version. BibRef 7907

Browning, J.D., and Tanimoto, S.L.,
Segmentation of Pictures into Regions with a Tile-by-Tile Method,
PR(15), No. 1, 1982, pp. 1-10.
WWW Version. Extension of split and merge to handle large images by looking at a small portion at one time. Grouping must allow for boundary conditions. BibRef 8200

Browning, J.D.,
A Method for Picture Segmentation by Parts: Split and Group with Linking,
PRAI-78(191). BibRef 7800

Chen, M.H., and Pavlidis, T.,
Image Seaming for Segmentation on Parallel Architecture,
PAMI(12), No. 6, June 1990, pp. 588-594.
IEEE Abstract.
WWW Version. Same problems as the above paper, but with architecture issues. BibRef 9006

Pavlidis, T., and Liow, Y.T.,
Integrating Region Growing and Edge Detection,
PAMI(12), No. 3, March 1990, pp. 225-233.
IEEE Abstract.
WWW Version. BibRef 9003
Earlier: CVPR88(208-214).
IEEE Abstract. Segmentation, Edges. Use edges in the merging portion of a split and merge segmentation algorithm. BibRef

Autonisse, H.J.,
Image Segmentation in Pyramids,
CGIP(19), No. 4, 1982, pp. 367-383. BibRef 8200

Spann, M., Wilson, R.,
A Quad-Tree Approach to Image Segmentation Which Combines Statistical and Spatial Information,
PR(18), No. 3-4, 1985, pp. 257-269.
WWW Version. BibRef 8500

Cheevasuvit, F., Maitre, H., and Vidal-Madjar, D.,
A Robust Method for Picture Segmentation Based on a Split-and-Merge Procedure,
CVGIP(34), No. 3, June 1986, pp. 268-281.
WWW Version. The aim is to get the consistent regions, the method is to segment all members of the sequence, reduce regions to an ellipse, and keep those regions whose ellipses are consistent. BibRef 8606

Laprade, R.H.,
Split-and-Merge Segmentation of Aerial Photographs,
CVGIP(44), No. 1, October 1988, pp. 77-86.
WWW Version. Lockheed work on segmentation. This uses a facet type representation of the resulting regions and the parameters are also used in the merge phase. BibRef 8810

Doherty, M.F., Bjorklund, C.M., and Noga, M.T.,
Split-Merge-merge: An Enhanced Segmentation Capability,
CVPR86(325-330). Add another merge step with more hueristics to eliminate the standard small region problems. BibRef 8600

Lee, C.H.[Chin-Hwa],
Recursive Region Splitting at Hierarchial Scope Views,
CVGIP(33), No. 2, February 1986, pp. 237-258.
WWW Version. BibRef 8602
And:
Image Surface Approximation with Irregular Samples,
PAMI(11), No. 2, February 1989, pp. 206-212.
IEEE Abstract.
WWW Version. Segmentation, Multi-Level. This method combines the regular splitting, and the quad-tree data structure of the split and merge techniques with the general threshold based region extraction method of the recursive splitting techniques. The main problem being addressed is how to merge the regions generated in one branch of the quad-tree with those in spatially adjacent branches of the tree. This requires an analysis of regions that touch the boundaries of the quad-tree nodes to determine how they should extend or connect to regions in the other nodes. BibRef

Imao, K.[Kaoru], Watanabe, H.[Hideyuki],
Method of describing image information,
US_Patent4,944,023, Jul 24, 1990
WWW Version. BibRef 9007

Wu, X.,
Adaptive Split-and-Merge Segmentation Based on Piecewise Least-Square Approximation,
PAMI(15), No. 8, August 1993, pp. 808-815.
IEEE Abstract.
WWW Version. BibRef 9308

Doherty, M.F., Noga, M.T., and Bjorklund, C.M.,
Use of Compound Predicates in Split-and-Merge Segmentation,
Lockheed Palo Alto Research Labs, CVPR85(659-661). Add constant texture measures to the standard splitting criteria. BibRef 8500

Cohen, Jr., E.A.[Edgar A.],
Generalized Sloped Facet Models Useful in Multispectral Image Analysis,
CVGIP(32), No. 2, November 1985, pp. 171-190.
WWW Version. Segmentation, Facet Model. Seems to combine split and merge techniques with the facet model for analysis. BibRef 8511

Jarvis, R.A.,
Computer Image Segmentation: First Partitions Using Shared Near Neighbor Clustering,
TC(20), No. 9, September 1971, pp. 1025-1034. BibRef 7109
And: Purdue-TR-77-43, November 1977. BibRef
And:
Computer Image Segmentation: Structured Merge Strategies,
Purdue-TR-77-44, November 1977. BibRef
And: (Similar title) Purdue-TR-75-45. Color. Bottom-up - image fragment conglomeration. Uses a variety of features and criteria to decide the merging of adjacent regions. Border count is one of them. Hard to predict the results analytically. Hypothesis concerning "low level" visual cohesion in intensity and color - excluding texture. (I.e., the region growing initialization step). (higher levels in TREE-75-44 and submitted for publication); neighborhood size, threshold of similarity rating; region grower initialization still same problem of using 8x8 elements as smallest element (no times given). (TC(20) is 1971, or is it TC(22)?) BibRef

Jarvis, R.A.,
Image Segmentation by Interactively Combining Line, Region, and Semantic Structure,
CGPR75(279-288). BibRef 7500

Jarvis, R.A.,
Shared Near Neighbor Maximal Spanning Trees for Cluster Analysis,
unknown location (UMd report?) Basic method: iteratively add the minimum link which adds a node to the tree. Add the least weight except when it causes a loop. Clustering: no unique optimal solution, any method gives different results on various non-linear transformations of measurement space. 7700
BibRef

Khan, G.N., Gillies, D.F.,
Parallel-Hierarchical Image Partitioning and Region Extraction,
CVIP92(123-140). BibRef 9200

Wu, Z., and Leahy, R.,
An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation,
PAMI(15), No. 11, November 1993, pp. 1101-1113.
IEEE Abstract.
WWW Version. BibRef 9311

Wu, Z., Leahy, R.,
Image segmentation via edge contour finding: a graph theoretic approach,
CVPR92(613-619).
IEEE Abstract. 0403
BibRef

Panjwani, D.K.[Dileep K.], Healey, G.,
Markov Random-Field Models for Unsupervised Segmentation of Textured Color Images,
PAMI(17), No. 10, October 1995, pp. 939-954.
IEEE Abstract.
WWW Version. Markov Random Field. Abstract:
HTML Version. BibRef 9510
And:
Erratta for Rotated Figures,
PAMI(17), No. 11, November 1995, pp. 1128-1128.
IEEE Top Reference. BibRef
Earlier:
Results Using Random Field Models for the Segmentation of Color Images,
ICCV95(714-719).
IEEE DOI Link
WWW Version. Segmentation, MRF. Color. Segmentation using split and merge type of algorithm. See also Analytical and Experimental Study of the Performance of Markov Random-Fields Applied to Textured Images Using Small Samples, An. BibRef

Panjwani, D.K., and Healey, G.,
Unsupervised Segmentation of Textured Color Images Using Markov Random Field Models,
CVPR93(776-777).
IEEE Abstract. BibRef 9300

Panjwani, D.K., and Healey, G.,
Selecting Neighbors in Random Field Models for Color Images,
ICIP94(II: 56-60).
IEEE DOI Link 9411
Abstract:
HTML Version. BibRef

Fiorio, C., and Gustedt, J.,
Two Linear Time Union-Find Strategies for Image Processing,
TCS(A: 154), No. 2, 1996, pp. 165-181. ON2 algorithm. BibRef 9600

Xu, Y., Uberbacher, E.C.,
2D Image Segmentation Using Minimum Spanning-Trees,
IVC(15), No. 1, January 1997, pp. 47-57.
WWW Version. 9702
BibRef

Li, C.T.,
Multiresolution image segmentation integrating Gibbs sampler and region merging algorithm,
SP(83), No. 1, January 2003, pp. 67-78.
HTML Version. 0211
BibRef

Li, C.T.[Chang-Tsun], Chiao, R.[Randy],
Multiresolution genetic clustering algorithm for texture segmentation,
IVC(21), No. 11, October 2003, pp. 955-966.
WWW Version. 0310
BibRef

Li, C.T.[Chang-Tsun], Chiao, R.,
Unsupervised texture segmentation using multiresolution hybrid genetic algorithm,
ICIP03(II: 1033-1036).
IEEE Abstract. 0312
BibRef

Storkey, A.J.[Amos J.], Williams, C.K.I.[Christopher K.I.],
Image modeling with position-encoding dynamic trees,
PAMI(25), No. 7, July 2003, pp. 859-871.
IEEE Abstract. 0307
Tree descriptions for segmentation. BibRef

Adams, N.J., Storkey, A.J., Ghahramani, Z., Williams, C.K.I.,
MFDTs: Mean Field Dynamic Trees,
ICPR00(Vol III: 147-150).
IEEE DOI Link
HTML Version. 0009
BibRef

Chung, K.L.[Kuo-Liang], Huang, H.L.[Hsu-Lien], Lu, H.I.[Hsueh-I],
Efficient region segmentation on compressed gray images using quadtree and shading representation,
PR(37), No. 8, August 2004, pp. 1591-1605.
WWW Version. 0407
Segment the compressed image, in split-merge tree framework. Compares to See also Two Linear Time Union-Find Strategies for Image Processing. BibRef

Chung, R.H.Y.[Ronald H.Y.], Yung, N.H.C.[Nelson H.C.], Cheung, P.Y.S.[Paul Y.S.],
An Efficient Parameterless Quadrilateral-Based Image Segmentation Method,
PAMI(27), No. 9, September 2005, pp. 1446-1458.
IEEE DOI Link 0508
BibRef

Grady, L.[Leo], Schwartz, E.L.[Eric L.],
Isoperimetric Graph Partitioning for Image Segmentation,
PAMI(28), No. 3, March 2006, pp. 469-475.
IEEE DOI Link 0602
BibRef
Earlier:
Faster graph-theoretic image processing via small-world and quadtree topologies,
CVPR04(II: 360-365).
IEEE Abstract. 0408
Segmentation approach. See also Random Walks for Image Segmentation. BibRef

Grady, L.[Leo],
Minimal Surfaces Extend Shortest Path Segmentation Methods to 3D,
PAMI(32), No. 2, February 2010, pp. 321-334.
IEEE DOI Link 1001
BibRef
Earlier:
Computing Exact Discrete Minimal Surfaces: Extending and Solving the Shortest Path Problem in 3D with Application to Segmentation,
CVPR06(I: 69-78).
IEEE DOI Link 0606
Segmentation, Range. BibRef

Grady, L.[Leo],
Fast, Quality, Segmentation of Large Volumes: Isoperimetric Distance Trees,
ECCV06(III: 449-462).
Springer DOI Link 0608
BibRef

Kumar, S., Ong, S.H., Ranganath, S., Ong, T.C., Chew, F.T.,
A rule-based approach for robust clump splitting,
PR(39), No. 6, June 2006, pp. 1088-1098.
WWW Version. 0604
Concavity analysis; Overlapping objects; Clump splitting BibRef

Pichel, J.C.[Juan C.], Singh, D.E.[David E.], Rivera, F.F.[Francisco F.],
Image segmentation based on merging of sub-optimal segmentations,
PRL(27), No. 10, 15 July 2006, pp. 1105-1116.
WWW Version. 0606
Region-merging heuristic; Segmentation evaluation BibRef

Duarte, A.[Abraham], Sánchez, Á.[Ángel], Fernández, F.[Felipe], Montemayor, A.S.[Antonio S.],
Improving image segmentation quality through effective region merging using a hierarchical social metaheuristic,
PRL(27), No. 11, August 2006, pp. 1239-1251.
WWW Version. Evolutionary metaheuristics; Watershed; Region merging; Graph-based segmentation; Hierarchical social algorithm 0606
BibRef

Ouzounis, G.K.[Georgios K.], Wilkinson, M.H.F.[Michael H.F.],
Mask-Based Second-Generation Connectivity and Attribute Filters,
PAMI(29), No. 6, June 2007, pp. 990-1004.
IEEE DOI Link 0704
BibRef
Earlier:
Countering Oversegmentation in Partitioning-Based Connectivities,
ICIP05(III: 844-847).
IEEE DOI Link 0512
BibRef

Kiwanuka, F.N.[Fred N.], Ouzounis, G.K.[Georgios K.], Wilkinson, M.H.F.[Michael H. F.],
Surface-Area-Based Attribute Filtering in 3D,
ISMM09(70-81).
Springer DOI Link 0908
BibRef

Ouzounis, G.K.[Georgios K.],
An Efficient Algorithm for Computing Multi-scale Connectivity Measures,
ISMM09(307-319).
Springer DOI Link 0908
BibRef

Wilkinson, M.H.F.[Michael H.F.],
An Axiomatic Approach to Hyperconnectivity,
ISMM09(35-46).
Springer DOI Link 0908
BibRef

Wilkinson, M.H.F.[Michael H.F.],
Hyperconnectivity, Attribute-Space Connectivity and Path Openings: Theoretical Relationships,
ISMM09(47-58).
Springer DOI Link 0908
BibRef

Wu, Y.T.[Yi-Ta], Shih, F.Y.[Frank Y.], Shi, J.Z.[Jia-Zheng], Wu, Y.T.[Yih-Tyng],
A top-down region dividing approach for image segmentation,
PR(41), No. 6, June 2008, pp. 1948-1960.
WWW Version. 0802
Image segmentation; Feature-based segmentation; Spatial-based segmentation; Watershed; Medical image analysis BibRef

Stewart, L.[Liam], He, X.M.[Xu-Ming], Zemel, R.S.[Richard S.],
Learning Flexible Features for Conditional Random Fields,
PAMI(30), No. 8, August 2008, pp. 1415-1426.
IEEE DOI Link 0806
hierarchical models. BibRef

He, X.M.[Xu-Ming], Zemel, R.S.[Richard S.], Ray, D.[Debajyoti],
Learning and Incorporating Top-Down Cues in Image Segmentation,
ECCV06(I: 338-351).
Springer DOI Link 0608
BibRef

Levin, A.[Anat], Weiss, Y.[Yair],
Learning to Combine Bottom-Up and Top-Down Segmentation,
IJCV(81), No. 1, January 2009, pp. xx-yy.
Springer DOI Link 0901
BibRef
Earlier: ECCV06(IV: 581-594).
Springer DOI Link 0608
BibRef

Zhang, R.G.[Rong-Guo], Xiao, B.H.[Bai-Hua], Wang, C.H.[Chun-Heng],
Oversegment an image to get the candidate detection windows,
ICIP09(845-848).
IEEE DOI Link 0911
BibRef

Atsumi, M.[Masayasu],
Attention-Based Segmentation on an Image Pyramid Sequence,
ACIVS08(xx-yy).
Springer DOI Link 0810
BibRef

Zeng, G.[Gang], Van Gool, L.J.[Luc J.],
Multi-label image segmentation via point-wise repetition,
CVPR08(1-8).
IEEE DOI Link 0806
BibRef

Baldacci, F.[Fabien], Braquelaire, A.[Achille], Damiand, G.[Guillaume],
3D Topological Map Extraction from Oriented Boundary Graph,
GbRPR09(283-292).
Springer DOI Link 0905
BibRef