Content deleted Content added
Line 1:
{{Short description|Partitioning a digital image into segments}}
{{Use dmy dates|date=November 2024}}
[[File:Model of a segmented femur - journal.pone.0079004.g005.png|thumb|Model of a segmented left human [[femur]]. It shows the outer surface (red), the surface between compact bone and spongy bone (green) and the surface of the bone marrow (blue).]]
In [[digital image processing]] and [[computer vision]], '''image segmentation''' is the process of partitioning a [[digital image]] into multiple '''image segments''', also known as '''image regions''' or '''image objects''' ([[Set (mathematics)|sets]] of [[pixel]]s). The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze.<ref name="computervision">[[Linda Shapiro|Linda G. Shapiro]] and George C. Stockman (2001): "Computer Vision", pp 279–325, New Jersey, Prentice-Hall, {{ISBN|0-13-030796-3}}</ref><ref>Barghout, Lauren, and Lawrence W. Lee. "Perceptual information processing system." Paravue Inc. U.S. Patent Application 10/618,543, filed
The result of image segmentation is a set of segments that collectively cover the entire image, or a set of [[Contour line|contour]]s extracted from the image (see [[edge detection]]). Each of the pixels in a region are similar with respect to some characteristic or computed property,<ref>{{cite conference | last1=Nielsen | first1=Frank | last2=Nock | first2=Richard
Line 18 ⟶ 19:
* [[Medical imaging]],<ref>{{cite journal | last1 = Pham | first1 = Dzung L. | last2 = Xu | first2 = Chenyang | last3 = Prince | first3 = Jerry L. | year = 2000 | title = Current Methods in Medical Image Segmentation | journal = Annual Review of Biomedical Engineering | volume = 2 | pages = 315–337 | pmid = 11701515 | doi = 10.1146/annurev.bioeng.2.1.315 }}</ref><ref>{{cite journal | last1 = Forghani| first1 = M. | last2 = Forouzanfar | first2 = M.| last3 = Teshnehlab| first3 = M. | year = 2010 | title = Parameter optimization of improved fuzzy c-means clustering algorithm for brain MR image segmentation | journal = Engineering Applications of Artificial Intelligence | volume = 23 | issue = 2 | pages = 160–168 | doi = 10.1016/j.engappai.2009.10.002 }}</ref> and imaging studies in biomedical research, including [[volume rendering|volume rendered]] images from [[CT scan|computed tomography]], [[magnetic resonance imaging]], as well as volume electron microscopy techniques such as FIB-SEM.<ref>{{Cite journal |last1=Reznikov |first1=Natalie |last2=Buss |first2=Dan J. |last3=Provencher |first3=Benjamin |last4=McKee |first4=Marc D. |last5=Piché |first5=Nicolas |date=October 2020 |title=Deep learning for 3D imaging and image analysis in biomineralization research |url=http://dx.doi.org/10.1016/j.jsb.2020.107598 |journal=Journal of Structural Biology |volume=212 |issue=1 |pages=107598 |doi=10.1016/j.jsb.2020.107598 |pmid=32783967 |s2cid=221126896 |issn=1047-8477}}</ref>
** Locate tumors and other pathologies<ref>{{cite journal | url=https://link.springer.com/article/10.1007/s11548-013-0922-7 | doi=10.1007/s11548-013-0922-7 | title=Brain tumor detection and segmentation in a CRF (Conditional random fields) framework with pixel-pairwise affinity and superpixel-level features | year=2014 | last1=Wu | first1=Wei | last2=Chen | first2=Albert Y. C. | last3=Zhao | first3=Liang | last4=Corso | first4=Jason J. | journal=International Journal of Computer Assisted Radiology and Surgery | volume=9 | issue=2 | pages=241–253 | pmid=23860630 | s2cid=13474403 }}</ref><ref>E. B. George and M. Karnan (2012): "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.411.7411&rep=rep1&type=pdf MR Brain image segmentation using Bacteria Foraging Optimization Algorithm]", ''International Journal of Engineering and Technology'', Vol. 4.</ref>
** Measure tissue volumes<ref>{{Cite journal |last1=Ye |first1=Run Zhou |last2=Noll |first2=Christophe |last3=Richard |first3=Gabriel |last4=Lepage |first4=Martin |last5=Turcotte |first5=Éric E. |last6=Carpentier |first6=André C. |date=February 2022 |title=DeepImageTranslator: A free, user-friendly graphical interface for image translation using deep-learning and its applications in 3D CT image analysis |journal=SLAS Technology |volume=27 |issue=1 |pages=76–84 |doi=10.1016/j.slast.2021.10.014 |pmid=35058205 |issn=2472-6303|doi-access=free }}</ref><ref>{{Cite journal |last1=Ye |first1=En Zhou |last2=Ye |first2=En Hui |last3=Bouthillier |first3=Maxime |last4=Ye |first4=Run Zhou |date=
** Diagnosis, study of anatomical structure<ref>{{cite journal|last1=Kamalakannan|first1=Sridharan|last2=Gururajan|first2=Arunkumar|last3=Sari-Sarraf|first3=Hamed|last4=Rodney|first4=Long|last5=Antani|first5=Sameer|title=Double-Edge Detection of Radiographic Lumbar Vertebrae Images Using Pressurized Open DGVF Snakes|journal=IEEE Transactions on Biomedical Engineering|date=17 February 2010|volume=57|issue=6|pages=1325–1334|doi=10.1109/tbme.2010.2040082|pmid=20172792|s2cid=12766600}}</ref>
** Surgery planning
** Virtual surgery simulation
** Intra-surgery navigation
** Radiotherapy<ref>{{Cite arXiv |last1=Georgescu |first1=Mariana-Iuliana |last2=Ionescu |first2=Radu Tudor |last3=Miron |first3=Andreea-Iuliana |date=
* [[Object detection]]<ref>J. A. Delmerico, P. David and J. J. Corso (2011): "[http://www.jeffdelmerico.com/wp-content/papercite-data/pdf/delmerico2011building.pdf Building façade detection, segmentation and parameter estimation for mobile robot localization and guidance]", International Conference on Intelligent Robots and Systems, pp. 1632–1639.</ref>
** [[Pedestrian detection]]
Line 57 ⟶ 58:
The key of this method is to select the threshold value (or values when multiple-levels are selected). Several popular methods are used in industry including the maximum entropy method, [[balanced histogram thresholding]], [[Otsu's method]] (maximum variance), and [[k-means clustering]].
Recently, methods have been developed for thresholding computed tomography (CT) images. The key idea is that, unlike Otsu's method, the thresholds are derived from the radiographs instead of the (reconstructed) image.<ref>{{cite journal |last1 = Batenburg |first1 = K J. |last2 = Sijbers |first2 = J. |year = 2009|title = Adaptive thresholding of tomograms by projection distance minimization |journal = Pattern Recognition |volume = 42 |issue = 10 |pages = 2297–2305 |doi = 10.1016/j.patcog.2008.11.027 |bibcode = 2009PatRe..42.2297B |citeseerx = 10.1.1.182.8483 }}</ref><ref>{{cite journal |first1 = K J. |last1 = Batenburg |first2 = J. |last2 = Sijbers |title = Optimal Threshold Selection for Tomogram Segmentation by Projection Distance Minimization |journal = IEEE Transactions on Medical Imaging |volume = 28 |issue = 5 |pages = 676–686 |date = June 2009 |url = http://www.visielab.ua.ac.be/publications/optimal-threshold-selection-tomogram-segmentation-projection-distance-minimization |format = PDF |doi = 10.1109/tmi.2008.2010437 |pmid = 19272989 |s2cid = 10994501 |access-date =
New methods suggested the usage of multi-dimensional fuzzy rule-based non-linear thresholds. In these works decision over each pixel's membership to a segment is based on multi-dimensional rules derived from fuzzy logic and evolutionary algorithms based on image lighting environment and application.<ref>{{cite book |first1 = A. |last1 = Kashanipour |first2 = N |last2 = Milani |first3 = A. |last3 = Kashanipour |first4 = H. |last4 = Eghrary |title = 2008 Congress on Image and Signal Processing |chapter = Robust Color Classification Using Fuzzy Rule-Based Particle Swarm Optimization |publisher = IEEE Congress on Image and Signal Processing |volume = 2 |pages = 110–114 |date = May 2008 |doi = 10.1109/CISP.2008.770 |isbn = 978-0-7695-3119-9 |s2cid = 8422475 }}</ref>
Line 100 ⟶ 101:
== Compression-based methods ==
Compression based methods postulate that the optimal segmentation is the one that minimizes, over all possible segmentations, the coding length of the data.<ref>{{cite journal |author1=Hossein Mobahi |author2=Shankar Rao |author3=Allen Yang |author4=Shankar Sastry |author5=Yi Ma. |url=http://perception.csl.illinois.edu/coding/papers/MobahiH2011-IJCV.pdf |title=Segmentation of Natural Images by Texture and Boundary Compression |journal=International Journal of Computer Vision |volume=95 |pages=86–98 |year=2011 |doi=10.1007/s11263-011-0444-0 |arxiv=1006.3679 |citeseerx=10.1.1.180.3579 |s2cid=11070572 |access-date=8 May 2011
# The boundary encoding leverages the fact that regions in natural images tend to have a smooth contour. This prior is used by [[Huffman coding]] to encode the difference [[chain code]] of the contours in an image. Thus, the smoother a boundary is, the shorter coding length it attains.
Line 160 ⟶ 161:
== Dual clustering method ==
This method is a combination of three characteristics of the image: partition of the image based on histogram analysis is checked by high compactness of the clusters (objects), and high gradients of their borders. For that purpose two spaces have to be introduced: one space is the one-dimensional histogram of brightness ''H'' = ''H''(''B''); the second space is the dual 3-dimensional space of the original image itself ''B'' = ''B''(''x'', ''y''). The first space allows to measure how compactly the brightness of the image is distributed by calculating a minimal clustering kmin. Threshold brightness T corresponding to kmin defines the binary (black-and-white) image – bitmap ''b'' = ''φ''(''x'', ''y''), where ''φ''(''x'', ''y'') = 0, if ''B''(''x'', ''y'') < ''T'', and ''φ''(''x'', ''y'') = 1, if ''B''(''x'', ''y'') ≥ ''T''. The bitmap ''b'' is an object in dual space. On that bitmap a measure has to be defined reflecting how compact distributed black (or white) pixels are. So, the goal is to find objects with good borders. For all ''T'' the measure ''M''<sub>DC</sub> = ''G''/(''k'' × ''L'') has to be calculated (where ''k'' is difference in brightness between the object and the background, ''L'' is length of all borders, and ''G'' is mean gradient on the borders). Maximum of MDC defines the segmentation.<ref>[http://gth.krammerbuch.at/sites/default/files/articles/AHAH%20callback/01_Guberman_KORR.pdf] {{Webarchive|url=https://web.archive.org/web/20171013224758/http://gth.krammerbuch.at/sites/default/files/articles/AHAH%20callback/01_Guberman_KORR.pdf|date=
== Region-growing methods ==
Line 178 ⟶ 179:
[[Split and merge segmentation|Split-and-merge segmentation]] is based on a [[quadtree]] partition of an image. It is sometimes called quadtree segmentation.
This method starts at the root of the tree that represents the whole image. If it is found non-uniform (not homogeneous), then it is split into four child squares (the splitting process), and so on. If, in contrast, four child squares are homogeneous, they are merged as several connected components (the merging process). The node in the tree is a segmented node. This process continues recursively until no further splits or merges are possible.<ref name="split-and-merge1">S.L. Horowitz and T. Pavlidis, Picture Segmentation by a Directed Split and Merge Procedure, Proc. ICPR, 1974, Denmark, pp. 424–433.</ref><ref name="split-and-merge2">S.L. Horowitz and T. Pavlidis, Picture Segmentation by a Tree Traversal Algorithm, Journal of the ACM, 23 (1976), pp. 368–388.</ref> When a special data structure is involved in the implementation of the algorithm of the method, its time complexity can reach <math>O(n\log n)</math>, an optimal algorithm of the method.<ref name="split-and-merge3">L. Chen, [http://www.spclab.com/research/lambda/lambdaConn91.pdf The lambda-connected segmentation and the optimal algorithm for split-and-merge segmentation] {{Webarchive|url=https://web.archive.org/web/20160310054934/http://www.spclab.com/research/lambda/lambdaConn91.pdf |date=
== Partial differential equation-based methods ==
Line 212 ⟶ 213:
== Graph partitioning methods ==
[[Graph (data structure)|Graph]] partitioning methods are an effective tools for image segmentation since they model the impact of pixel neighborhoods on a given cluster of pixels or pixel, under the assumption of homogeneity in images. In these methods, the image is modeled as a weighted, [[undirected graph]]. Usually a pixel or a group of pixels are associated with [[Vertex (graph theory)|nodes]] and [[Glossary of graph theory#Basics|edge]] weights define the (dis)similarity between the neighborhood pixels. The graph (image) is then partitioned according to a criterion designed to model "good" clusters. Each partition of the nodes (pixels) output from these algorithms are considered an object segment in the image; see [[Segmentation-based object categorization]]. Some popular algorithms of this category are normalized cuts,<ref>Jianbo Shi and [[Jitendra Malik]] (2000): [https://www.cs.cmu.edu/~jshi/papers/pami_ncut.pdf "Normalized Cuts and Image Segmentation"], ''IEEE Transactions on Pattern Analysis and Machine Intelligence'', pp 888–905, Vol. 22, No. 8</ref> [[random walker (computer vision)|random walker]],<ref>Leo Grady (2006): [http://vision.cse.psu.edu/people/chenpingY/paper/grady2006random.pdf "Random Walks for Image Segmentation"], ''IEEE Transactions on Pattern Analysis and Machine Intelligence'', pp. 1768–1783, Vol. 28, No. 11</ref> minimum cut,<ref>Z. Wu and R. Leahy (1993): [ftp://sipi.usc.edu/pub/leahy/pdfs/MAP93.pdf "An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation"]{{Dead link|date=January 2020 |bot=InternetArchiveBot |fix-attempted=yes }}, ''IEEE Transactions on Pattern Analysis and Machine Intelligence'', pp. 1101–1113, Vol. 15, No. 11</ref> isoperimetric partitioning,<ref>Leo Grady and Eric L. Schwartz (2006): [http://www.cns.bu.edu/~lgrady/grady2006isoperimetric.pdf "Isoperimetric Graph Partitioning for Image Segmentation"] {{Webarchive|url=https://web.archive.org/web/20110719090404/http://www.cns.bu.edu/~lgrady/grady2006isoperimetric.pdf |date=
=== Markov random fields ===
Line 334 ⟶ 335:
Lindeberg<ref>[http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A472969&dswid=2693 Lindeberg, T.: Detecting salient blob-like image structures and their scales with a scale-space primal sketch: A method for focus-of-attention, International Journal of Computer Vision, 11(3), 283–318, 1993.]</ref><ref name=lin94>[http://www.csc.kth.se/~tony/book.html Lindeberg, Tony, Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, 1994], {{ISBN|0-7923-9418-6}}</ref> studied the problem of linking local extrema and saddle points over scales, and proposed an image representation called the scale-space primal sketch which makes explicit the relations between structures at different scales, and also makes explicit which image features are stable over large ranges of scale including locally appropriate scales for those. Bergholm proposed to detect edges at coarse scales in scale-space and then trace them back to finer scales with manual choice of both the coarse detection scale and the fine localization scale.
Gauch and Pizer<ref>[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=628490 Gauch, J. and Pizer, S.: Multiresolution analysis of ridges and valleys in grey-scale images, IEEE Transactions on Pattern Analysis and Machine Intelligence, 15:6 (June 1993), pages: 635–646, 1993.]</ref> studied the complementary problem of ridges and valleys at multiple scales and developed a tool for interactive image segmentation based on multi-scale watersheds. The use of multi-scale watershed with application to the gradient map has also been investigated by Olsen and Nielsen<ref>Olsen, O. and Nielsen, M.: [https://link.springer.com/content/pdf/10.1007/3-540-63507-6_178.pdf Multi-scale gradient magnitude watershed segmentation], Proc. of ICIAP 97, Florence, Italy, Lecture Notes in Computer Science, pages 6–13. Springer Verlag, September 1997.</ref> and been carried over to clinical use by Dam.<ref>Dam, E., Johansen, P., Olsen, O. Thomsen,, A. Darvann, T., Dobrzenieck, A., Hermann, N., Kitai, N., Kreiborg, S., Larsen, P., Nielsen, M.: "Interactive multi-scale segmentation in clinical use" in European Congress of Radiology 2000.</ref> Vincken et al.<ref>{{Cite journal |doi=10.1109/34.574787 |title=Probabilistic multiscale image segmentation |year=1997 |last1=Vincken |first1=K.L. |last2=Koster |first2=A.S.E. |last3=Viergever |first3=M.A. |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=19 |issue=2 |pages=109–120 }}</ref> proposed a hyperstack for defining probabilistic relations between image structures at different scales. The use of stable image structures over scales has been furthered by Ahuja<ref>[http://vision.ai.uiuc.edu/~msingh/segmen/seg/MSS.html M. Tabb and N. Ahuja, Unsupervised multiscale image segmentation by integrated edge and region detection, IEEE Transactions on Image Processing, Vol. 6, No. 5, 642–655, 1997.] {{webarchive |url=https://web.archive.org/web/20110720084911/http://vision.ai.uiuc.edu/~msingh/segmen/seg/MSS.html |date=
These ideas for multi-scale image segmentation by linking image structures over scales have also been picked up by Florack and Kuijper.<ref>Florack, L. and Kuijper, A.: The topological structure of scale-space images, Journal of Mathematical Imaging and Vision, 12:1, 65–79, 2000.</ref> Bijaoui and Rué<ref>{{cite journal | last1 = Bijaoui | first1 = A. | last2 = Rué | first2 = F. | year = 1995 | title = A Multiscale Vision Model | journal = Signal Processing | volume = 46 | issue = 3| page = 345 | doi=10.1016/0165-1684(95)00093-4}}</ref> associate structures detected in scale-space above a minimum noise threshold into an object tree which spans multiple scales and corresponds to a kind of feature in the original signal. Extracted features are accurately reconstructed using an iterative conjugate gradient matrix method.
Line 379 ⟶ 380:
<!-- {{reflist|2}} -->
{{reflist|refs=
<ref name="Wang Duan Zhang Niu p=1657">{{cite journal | last1=Wang | first1=Le | last2=Duan | first2=Xuhuan | last3=Zhang | first3=Qilin | last4=Niu | first4=Zhenxing | last5=Hua | first5=Gang | last6=Zheng | first6=Nanning | title=Segment-Tube: Spatio-Temporal Action Localization in Untrimmed Videos with Per-Frame Segmentation | journal=Sensors | volume=18 | issue=5 | date=
<ref name="Liu Wang Hua Zhang 2018 pp. 5840–5853">{{cite journal | last1=Liu | first1=Ziyi | last2=Wang | first2=Le | last3=Hua | first3=Gang | last4=Zhang | first4=Qilin | last5=Niu | first5=Zhenxing | last6=Wu | first6=Ying | last7=Zheng | first7=Nanning | title=Joint Video Object Discovery and Segmentation by Coupled Dynamic Markov Networks | journal=IEEE Transactions on Image Processing | volume=27 | issue=12 | year=2018 | issn=1057-7149 | doi=10.1109/tip.2018.2859622 | pmid=30059300 | bibcode=2018ITIP...27.5840L | pages=5840–5853 | s2cid=51867241 | url=https://qilin-zhang.github.io/_pages/pdfs/Joint_Video_Object_Discovery_and_Segmentation_by_Coupled_Dynamic_Markov_Networks.pdf| doi-access=free }}</ref>
Line 394 ⟶ 395:
* [https://web.archive.org/web/20100518124644/http://csc.fsksm.utm.my/syed/projects/image-processing.html Some sample code that performs basic segmentation], by Syed Zainudeen. University Technology of Malaysia.
* [https://rd.springer.com/article/10.1007/s11075-008-9183-x Generalized Fast Marching method] by Forcadel et al. [2008] for applications in image segmentation.
* [http://www.iprg.co.in Image Processing Research Group] {{Webarchive|url=https://web.archive.org/web/20201228051352/http://www.iprg.co.in/ |date=
* [https://www.mathworks.com/discovery/image-segmentation.html Segmentation methods in image processing and analysis] and [https://blogs.mathworks.com/pick/2017/12/07/minimizing-energy-to-segment-images-or-cluster-data/ Minimizing energy to segment images] by Mathworks
* [http://disp.ee.ntu.edu.tw/meeting/%E6%98%B1%E7%BF%94/Segmentation%20tutorial.pdf More image segmentation methods with detailed algorithms] {{Webarchive|url=https://web.archive.org/web/20191101050028/http://disp.ee.ntu.edu.tw/meeting/%E6%98%B1%E7%BF%94/Segmentation%20tutorial.pdf |date=1 November 2019
* [https://ipolcore.ipol.im/demo/clientApp/demo.html?id=295 Online demonstration of piecewise linear image segmentation] by IPOL Journal
{{Authority control}}
| |||