Loading…
Computation complexity of branch-and-bound model selection
Segmentation problems are one of the most important areas of research in computer vision. While segmentation problems are generally solved with clustering paradigms, they formulate the problem as recursive. Additionally, most approaches need the number of clusters to be known beforehand. This requir...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Conference Proceeding |
| Language: | English |
| Subjects: | |
| Online Access: | Request full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | |
|---|---|
| cites | |
| container_end_page | 1900 |
| container_issue | |
| container_start_page | 1895 |
| container_title | |
| container_volume | |
| creator | Thakoor, Ninad Devarajan, Venkat Gao, Jean |
| description | Segmentation problems are one of the most important areas of research in computer vision. While segmentation problems are generally solved with clustering paradigms, they formulate the problem as recursive. Additionally, most approaches need the number of clusters to be known beforehand. This requirement is unreasonable for majority of the computer vision problems. This paper analyzes the model selection perspective which can overcome these limitations. Under this framework multiple hypotheses for cluster centers are generated using spatially coherent sampling. An optimal subset of these hypotheses is selected according to a model selection criterion. The selection can be carried out with a branch-and-bound procedure. The worst case complexity of any branch-and-bound algorithm is exponential. However, the average complexity of the algorithm is significantly lower. In this paper, we develop a framework for analysis of average complexity of the algorithm from the statistics of model selection costs. |
| doi_str_mv | 10.1109/ICCV.2009.5459420 |
| format | conference_proceeding |
| fullrecord | <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_5459420</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>5459420</ieee_id><sourcerecordid>5459420</sourcerecordid><originalsourceid>FETCH-LOGICAL-i175t-4115b071ce6dce3d59de034e8766f8fce48e3f53c0ab998f6cc5cbfc645072263</originalsourceid><addsrcrecordid>eNotkEtLw0AUhccXmNb-AHGTPzDxzuPOw50EH4WCG3Vbkpk7GEmTkqRg_70VczbnwHc4i8PYrYBCCPD367L8LCSAL1Cj1xLO2EJoqU8SHs9ZJpUDbhH0BVt562YmAS9ZJhCBo_b-mi3G8RtAeelMxh7Kfrc_TNXU9F0eTrmln2Y65n3K66Hqwhevusjr_tDFfNdHavORWgp_9Rt2lap2pNXsS_bx_PRevvLN28u6fNzwRlicuBYCa7AikImBVEQfCZQmZ41JLgXSjlRCFaCqvXfJhIChTsFoBCulUUt297_bENF2PzS7ajhu5w_UL5PATAk</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Computation complexity of branch-and-bound model selection</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Thakoor, Ninad ; Devarajan, Venkat ; Gao, Jean</creator><creatorcontrib>Thakoor, Ninad ; Devarajan, Venkat ; Gao, Jean</creatorcontrib><description>Segmentation problems are one of the most important areas of research in computer vision. While segmentation problems are generally solved with clustering paradigms, they formulate the problem as recursive. Additionally, most approaches need the number of clusters to be known beforehand. This requirement is unreasonable for majority of the computer vision problems. This paper analyzes the model selection perspective which can overcome these limitations. Under this framework multiple hypotheses for cluster centers are generated using spatially coherent sampling. An optimal subset of these hypotheses is selected according to a model selection criterion. The selection can be carried out with a branch-and-bound procedure. The worst case complexity of any branch-and-bound algorithm is exponential. However, the average complexity of the algorithm is significantly lower. In this paper, we develop a framework for analysis of average complexity of the algorithm from the statistics of model selection costs.</description><identifier>ISSN: 1550-5499</identifier><identifier>ISBN: 9781424444205</identifier><identifier>ISBN: 1424444209</identifier><identifier>EISSN: 2380-7504</identifier><identifier>EISBN: 1424444195</identifier><identifier>EISBN: 9781424444199</identifier><identifier>DOI: 10.1109/ICCV.2009.5459420</identifier><language>eng</language><publisher>IEEE</publisher><subject>Algorithm design and analysis ; Clustering algorithms ; Computational complexity ; Computer science ; Computer vision ; Cost function ; Image segmentation ; Motion segmentation ; Sampling methods ; Spatial coherence</subject><ispartof>2009 IEEE 12th International Conference on Computer Vision, 2009, p.1895-1900</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/5459420$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,27925,54555,54920,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/5459420$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Thakoor, Ninad</creatorcontrib><creatorcontrib>Devarajan, Venkat</creatorcontrib><creatorcontrib>Gao, Jean</creatorcontrib><title>Computation complexity of branch-and-bound model selection</title><title>2009 IEEE 12th International Conference on Computer Vision</title><addtitle>ICCV</addtitle><description>Segmentation problems are one of the most important areas of research in computer vision. While segmentation problems are generally solved with clustering paradigms, they formulate the problem as recursive. Additionally, most approaches need the number of clusters to be known beforehand. This requirement is unreasonable for majority of the computer vision problems. This paper analyzes the model selection perspective which can overcome these limitations. Under this framework multiple hypotheses for cluster centers are generated using spatially coherent sampling. An optimal subset of these hypotheses is selected according to a model selection criterion. The selection can be carried out with a branch-and-bound procedure. The worst case complexity of any branch-and-bound algorithm is exponential. However, the average complexity of the algorithm is significantly lower. In this paper, we develop a framework for analysis of average complexity of the algorithm from the statistics of model selection costs.</description><subject>Algorithm design and analysis</subject><subject>Clustering algorithms</subject><subject>Computational complexity</subject><subject>Computer science</subject><subject>Computer vision</subject><subject>Cost function</subject><subject>Image segmentation</subject><subject>Motion segmentation</subject><subject>Sampling methods</subject><subject>Spatial coherence</subject><issn>1550-5499</issn><issn>2380-7504</issn><isbn>9781424444205</isbn><isbn>1424444209</isbn><isbn>1424444195</isbn><isbn>9781424444199</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2009</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotkEtLw0AUhccXmNb-AHGTPzDxzuPOw50EH4WCG3Vbkpk7GEmTkqRg_70VczbnwHc4i8PYrYBCCPD367L8LCSAL1Cj1xLO2EJoqU8SHs9ZJpUDbhH0BVt562YmAS9ZJhCBo_b-mi3G8RtAeelMxh7Kfrc_TNXU9F0eTrmln2Y65n3K66Hqwhevusjr_tDFfNdHavORWgp_9Rt2lap2pNXsS_bx_PRevvLN28u6fNzwRlicuBYCa7AikImBVEQfCZQmZ41JLgXSjlRCFaCqvXfJhIChTsFoBCulUUt297_bENF2PzS7ajhu5w_UL5PATAk</recordid><startdate>200909</startdate><enddate>200909</enddate><creator>Thakoor, Ninad</creator><creator>Devarajan, Venkat</creator><creator>Gao, Jean</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>200909</creationdate><title>Computation complexity of branch-and-bound model selection</title><author>Thakoor, Ninad ; Devarajan, Venkat ; Gao, Jean</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i175t-4115b071ce6dce3d59de034e8766f8fce48e3f53c0ab998f6cc5cbfc645072263</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2009</creationdate><topic>Algorithm design and analysis</topic><topic>Clustering algorithms</topic><topic>Computational complexity</topic><topic>Computer science</topic><topic>Computer vision</topic><topic>Cost function</topic><topic>Image segmentation</topic><topic>Motion segmentation</topic><topic>Sampling methods</topic><topic>Spatial coherence</topic><toplevel>online_resources</toplevel><creatorcontrib>Thakoor, Ninad</creatorcontrib><creatorcontrib>Devarajan, Venkat</creatorcontrib><creatorcontrib>Gao, Jean</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Thakoor, Ninad</au><au>Devarajan, Venkat</au><au>Gao, Jean</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Computation complexity of branch-and-bound model selection</atitle><btitle>2009 IEEE 12th International Conference on Computer Vision</btitle><stitle>ICCV</stitle><date>2009-09</date><risdate>2009</risdate><spage>1895</spage><epage>1900</epage><pages>1895-1900</pages><issn>1550-5499</issn><eissn>2380-7504</eissn><isbn>9781424444205</isbn><isbn>1424444209</isbn><eisbn>1424444195</eisbn><eisbn>9781424444199</eisbn><abstract>Segmentation problems are one of the most important areas of research in computer vision. While segmentation problems are generally solved with clustering paradigms, they formulate the problem as recursive. Additionally, most approaches need the number of clusters to be known beforehand. This requirement is unreasonable for majority of the computer vision problems. This paper analyzes the model selection perspective which can overcome these limitations. Under this framework multiple hypotheses for cluster centers are generated using spatially coherent sampling. An optimal subset of these hypotheses is selected according to a model selection criterion. The selection can be carried out with a branch-and-bound procedure. The worst case complexity of any branch-and-bound algorithm is exponential. However, the average complexity of the algorithm is significantly lower. In this paper, we develop a framework for analysis of average complexity of the algorithm from the statistics of model selection costs.</abstract><pub>IEEE</pub><doi>10.1109/ICCV.2009.5459420</doi><tpages>6</tpages></addata></record> |
| fulltext | fulltext_linktorsrc |
| identifier | ISSN: 1550-5499 |
| ispartof | 2009 IEEE 12th International Conference on Computer Vision, 2009, p.1895-1900 |
| issn | 1550-5499 2380-7504 |
| language | eng |
| recordid | cdi_ieee_primary_5459420 |
| source | IEEE Electronic Library (IEL) Conference Proceedings |
| subjects | Algorithm design and analysis Clustering algorithms Computational complexity Computer science Computer vision Cost function Image segmentation Motion segmentation Sampling methods Spatial coherence |
| title | Computation complexity of branch-and-bound model selection |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-05T07%3A02%3A26IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Computation%20complexity%20of%20branch-and-bound%20model%20selection&rft.btitle=2009%20IEEE%2012th%20International%20Conference%20on%20Computer%20Vision&rft.au=Thakoor,%20Ninad&rft.date=2009-09&rft.spage=1895&rft.epage=1900&rft.pages=1895-1900&rft.issn=1550-5499&rft.eissn=2380-7504&rft.isbn=9781424444205&rft.isbn_list=1424444209&rft_id=info:doi/10.1109/ICCV.2009.5459420&rft.eisbn=1424444195&rft.eisbn_list=9781424444199&rft_dat=%3Cieee_6IE%3E5459420%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i175t-4115b071ce6dce3d59de034e8766f8fce48e3f53c0ab998f6cc5cbfc645072263%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=5459420&rfr_iscdi=true |