Level-set method

Video of spiral being propagated by level sets (curvature flow) in 2D. Left image shows zero-level solution. Right image shows the level-set scalar field.

The Level-set method (LSM) is a conceptual framework for using level sets as a tool for numerical analysis of surfaces and shapes. LSM can perform numerical computations involving curves and surfaces on a fixed Cartesian grid without having to parameterize these objects.[1] LSM makes it easier to perform computations on shapes with sharp corners and shapes that change topology (such as by splitting in two or developing holes). These characteristics make LSM effective for modeling objects that vary in time, such as an airbag inflating or a drop of oil floating in water.

An illustration of the level-set method

Overview

The figure on the right illustrates several ideas about LSM. In the upper left corner is a bounded region with a well-behaved boundary. Below it, the red surface is the graph of a level set function determining this shape, and the flat blue region represents the X-Y plane. The boundary of the shape is then the zero-level set of , while the shape itself is the set of points in the plane for which is positive (interior of the shape) or zero (at the boundary).

In the top row, the shape's topology changes as it is split in two. It is challenging to describe this transformation numerically by parameterizing the boundary of the shape and following its evolution. An algorithm can be used to detect the moment the shape splits in two and then construct parameterizations for the two newly obtained curves. On the bottom row, however, the plane at which the level set function is sampled is translated upwards, on which the shape's change in topology is described. It is less challenging to work with a shape through its level-set function rather than with itself directly, in which a method would need to consider all the possible deformations the shape might undergo.

Thus, in two dimensions, the level-set method amounts to representing a closed curve (such as the shape boundary in our example) using an auxiliary function , called the level-set function. The curve is represented as the zero-level set of by

and the level-set method manipulates implicitly through the function . This function is assumed to take positive values inside the region delimited by the curve and negative values outside.[2][3]

The level-set equation

If the curve moves in the normal direction with a speed , then by chain rule and implicit differentiation, it can be determined that the level-set function satisfies the level-set equation

Here, is the Euclidean norm (denoted customarily by single bars in partial differential equations), and is time. This is a partial differential equation, in particular a Hamilton–Jacobi equation, and can be solved numerically, for example, by using finite differences on a Cartesian grid.[2][3]

However, the numerical solution of the level set equation may require advanced techniques. Simple finite difference methods fail quickly. Upwinding methods such as the Godunov method are considered better; however, the level set method does not guarantee preservation of the volume and shape of the set level in an advection field that maintains shape and size, for example, a uniform or rotational velocity field. Instead, the shape of the level set may become distorted, and the level set may disappear over a few time steps. Therefore, high-order finite difference schemes, such as high-order essentially non-oscillatory (ENO) schemes, are often required, and even then, the feasibility of long-term simulations is questionable. More advanced methods have been developed to overcome this; for example, combinations of the leveling method with tracking marker particles suggested by the velocity field.[4]

Example

Consider a unit circle in , shrinking in on itself at a constant rate, i.e. each point on the boundary of the circle moves along its inwards pointing normally at some fixed speed. The circle will shrink and eventually collapse down to a point. If an initial distance field is constructed (i.e. a function whose value is the signed Euclidean distance to the boundary, positive interior, negative exterior) on the initial circle, the normalized gradient of this field will be the circle normal.

If the field has a constant value subtracted from it in time, the zero level (which was the initial boundary) of the new fields will also be circular and will similarly collapse to a point. This is due to this being effectively the temporal integration of the Eikonal equation with a fixed front velocity.

Applications

History

The level-set method was developed in 1979 by Alain Dervieux,[5] and subsequently popularized by Stanley Osher and James Sethian. It has since become popular in many disciplines, such as image processing, computer graphics, computational geometry, optimization, computational fluid dynamics, and computational biology.

See also

References

  1. ^ Osher, S.; Sethian, J. A. (1988), "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton–Jacobi formulations" (PDF), J. Comput. Phys., 79 (1): 12–49, Bibcode:1988JCoPh..79...12O, CiteSeerX 10.1.1.46.1266, doi:10.1016/0021-9991(88)90002-2, hdl:10338.dmlcz/144762, S2CID 205007680
  2. ^ a b Osher, Stanley J.; Fedkiw, Ronald P. (2002). Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag. ISBN 978-0-387-95482-0.
  3. ^ a b Sethian, James A. (1999). Level Set Methods and Fast Marching Methods : Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press. ISBN 978-0-521-64557-7.
  4. ^ Enright, D.; Fedkiw, R. P.; Ferziger, J. H.; Mitchell, I. (2002), "A hybrid particle level set method for improved interface capturing" (PDF), J. Comput. Phys., 183 (1): 83–116, Bibcode:2002JCoPh.183...83E, CiteSeerX 10.1.1.15.910, doi:10.1006/jcph.2002.7166
  5. ^ Dervieux, A.; Thomasset, F. (1980). "A finite element method for the simulation of a Rayleigh-Taylor instability". Approximation Methods for Navier-Stokes Problems. Lecture Notes in Mathematics. Vol. 771. Springer. pp. 145–158. doi:10.1007/BFb0086904. ISBN 978-3-540-38550-9.

Read other articles:

Ten artykuł od 2022-01 zawiera treści, przy których brakuje odnośników do źródeł.Należy dodać przypisy do treści niemających odnośników do wiarygodnych źródeł.(Dodanie listy źródeł bibliograficznych lub linków zewnętrznych nie jest wystarczające).Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • RCIN • Internet Archive (texts / in...

 

بطرس الخامس معلومات شخصية مكان الميلاد مصر  الوفاة 8 يوليو 1348  مصر  مكان الدفن كنيسة السيدة العذراء مريم بابليون الدرج الأثرية  الجنسية مصري الحياة العملية الكنيسة الكنيسة القبطية الأرثوذكسية معلومات شخصية الاسم عند الولادة بطرس بن داود الوفاة 14 أبيب 1064 ش / 6 يولي...

 

سيغفريد بريتزكه (بالألمانية: Siegfried Brietzke)‏    معلومات شخصية الميلاد 12 يونيو 1952 (العمر 71 سنة)روستوك  مواطنة ألمانيا ألمانيا الشرقية  الطول 192 سنتيمتر  الحياة العملية المهنة مجدف  اللغات الألمانية  الرياضة التجديف  بلد الرياضة ألمانيا الشرقية  تعديل مصدر...

Наука в Польщі – всі наукові дослідження та розробки, що проводяться в Польщі з точних наук, природничих наук, гуманітарних наук, технологій, мистецтва та філософії. Зміст 1 Історія 2 Наукова кар'єра 3 Фінансування науки 4 Примітки 5 Див. також 6 Бібліографія 7 Посилання Істо...

 

الذاكرة الاستعادية (بالإنجليزية: Retrospective memory) هي ذاكرة الناس، والكلمات، والأحداث المصادفة والمجربة في الماضي. تشمل جميع أنواع الذاكرة بما فيها العرضية والدلالية والإجرائية. قد تكون ضمنية أو صريحة.[1] وفي المقابل، تتضمن الذاكرة الاستباقية تذكُّر شيء ما أو إنجاز شيء ما ب...

 

Kontributor utama artikel ini tampaknya memiliki hubungan dekat dengan subjek. Artikel ini mungkin memerlukan perapian untuk mematuhi kebijakan konten Wikipedia, terutama dalam hal sudut pandang netral. Silakan dibahas lebih lanjut di halaman pembicaraan artikel ini. Artikel ini tidak memiliki referensi atau pranala luar ke sumber-sumber tepercaya yang dapat menyatakan kelayakan dari subyek yang dibahas.(ajukan diskusi keberatan penghapusan)Artikel ini akan dihapus pada 17 November 2023 ...

التهاب الحساسية الزائدة الرئوي صورة مجهرية بتكبير عالٍ تظهر عينة من رئة مريض مصاب التهاب الحساسية الزائدة المزمن، يلاحظ وجود توسع طفيف في جدار الحويصلات بفعل الخلايا اللمفاوية. وجود خلية عملاقة متعددة الأنوية في النسيج الخلالي يعد أحد الظواهر التي تؤكد على صحة التشخيص .ص...

 

Nature tourism Cocos Island is a prime ecotourism destination in Costa Rica. A World Heritage Site, ranked among the top 77 nominees for the New 7 Wonders of Nature.[1] Ecotourism is a key component of the tourism industry in Costa Rica. By the early 1990s, Costa Rica became known as the poster child of ecotourism.[2] The country is among many developing nations that look to ecotourism as a way of cashing in on the growing demand for this popular trend of travel.[3] Ec...

 

Fictional character from Cars franchise Fictional character Lightning McQueenCars characterLightning McQueen, as he appears in Cars wearing his rookie paint jobFirst appearanceCars (2006)Created byJohn LasseterJoe RanftJorgen KlubienVoiced byOwen Wilson (films, Cars: The Video Game, Mater and the Ghostlight, Cars Toons: Tales from Radiator Springs, and Cars on the Road) Keith Ferguson (most video games, Cars Toons: Mater's Tall Tales, Cars Toons: Tales from Radiator Springs, and Miss Fritter'...

Gathering of Indigenous leaders in Alaska This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Tanana Chiefs Conference – news · newspapers · books · scholar · JSTOR (January 2009) (Learn how and when to remove this template message) Tanana Chiefs Conference (TCC), the traditional tribal consortium of the 42 villages of Interior Alaska, is based on a belief ...

 

此條目需要补充更多来源。 (2023年2月12日)请协助補充多方面可靠来源以改善这篇条目,无法查证的内容可能會因為异议提出而被移除。致使用者:请搜索一下条目的标题(来源搜索:卡拉傑克矩陣 — 网页、新闻、书籍、学术、图像),以检查网络上是否存在该主题的更多可靠来源(判定指引)。 卡拉傑克矩陣(Kraljic Matrix)的中文翻譯 战略 主要面向 战略 · 战略管...

 

39°33′42″N 121°21′20″W / 39.561638°N 121.35548°W / 39.561638; -121.35548 Location of Enterprise Rancheria Enterprise Rancheria is the landbase for the Estom Yumeka Maidu Tribe, located in Butte County, near Oroville, California.[1] The nearest outside communities are Berry Creek and Forbestown. As of the 2010 Census the population was 1.[2] The Estom Yumeka Maidu Tribe itself has around 1000 citizens.[3] References ^ U.S. Geological ...

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Borders of France – news · newspapers · books · scholar · JSTOR (October 2018) (Learn how and when to remove this template message) Political boundaries between France and neighboring territories France and its territories The French Republic[1] has ter...

 

Magnetic diffusion refers to the motion of magnetic fields, typically in the presence of a conducting solid or fluid such as a plasma. The motion of magnetic fields is described by the magnetic diffusion equation and is due primarily to induction and diffusion of magnetic fields through the material. The magnetic diffusion equation is a partial differential equation commonly used in physics. Understanding the phenomenon is essential to magnetohydrodynamics and has important consequences in as...

 

Russian particle physicist Vladimir LobashevBornVladimir Mikhailovich Lobashev(1934-07-29)July 29, 1934Leningrad, RSFSR, Soviet UnionDiedAugust 3, 2011(2011-08-03) (aged 77)NationalityRussianEducationSaint Petersburg State UniversityKnown forP and CP invariance; neutron and neutrino physicsAwardsLenin Prize 1974Order of the Red Banner of Labour 1984Bruno Pontecorvo Prize 1998Scientific careerFieldsNuclear physics, particle physicsInstitutionsIoffe Institute, Saint Petersburg Institu...

Augusto de Prima Porta, Museos Vaticanos. La escultura de Roma se desarrolló en toda la zona de este país de influencia romana, con su foco central en Roma , entre el siglo VI a. C. y V d. C.[1]​ El origen derivó de la escultura griega, principalmente a través de la herencia de la escultura etrusca, y luego directamente, por contacto con las colonias de la Magna Grecia y la propia Grecia, durante el periodo helenístico.[2]​[3]​ El retrato, género que consigui...

 

City in IsraelKiryat Motzkin קִרְיַת מוֹצְקִין‎CityHebrew transcription(s) • ISO 259Qiryat Móçqin (Motzkin) • Also spelledKiryat Motzkin (unofficial)Kiryat Motzkin Municipality building Kiryat MotzkinShow map of Haifa region of IsraelKiryat MotzkinShow map of IsraelCoordinates: 32°50′N 35°05′E / 32.833°N 35.083°E / 32.833; 35.083Country IsraelDistrict HaifaFounded1934Government • MayorHa...

 

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Maret 2016. SMA Negeri 1 KotabumiInformasiJurusan atau peminatanIPA dan IPSRentang kelasX IPA, X IPS, XI IPA, XI IPS, XII IPA, XII IPSKurikulumKurikulum 2013AlamatLokasiJl. Ganesha 5, Kota Kotabumi, LampungMoto SMA Negeri (SMAN) 1 Kotabumi, merupakan salah satu Seko...

Vietnamese shamanic ritual The lên đồng ritual in process. Múa mồi (fire dance) in lên đồng ritual. Lên đồng (Vietnamese: [len ɗə̂wŋm], chữ Nôm: 𨖲童), votive dance, to mount the medium,[1] or going into trance[2]) is a ritual practiced in Vietnamese folk religion, in which followers become spirit mediums for various kinds of spirits. There is a common confusion between lên đồng and hầu bóng (which is the most prominent ritual of Đạo ...

 

台湾の歴史 台湾史年表 先史時代オランダ統治時代(1624-1662)鄭氏政権 (1662-1683)清朝統治時代 (1683-1895)台湾民主国 (1895)日本統治時代 (1895-1945)中華民国統治時代 (1945-現在) 政治史経済史建築史(十大土木史蹟 - 百大建設)文化史社会史教育史メディア史軍事史交通史中台関係 台北の歴史高雄の歴史 台湾古跡一覧遺跡参考 中国の歴史中華民国の歴史その他台湾に関する記事 ...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!