자동 라벨 배치

자동 라벨 배치(텍스트 배치 또는 이름 배치라고도 함)는 지도 또는 차트에 라벨을 자동으로 배치하는 컴퓨터 방법으로 구성됩니다.이는 이러한 라벨의 인쇄 디자인과 관련이 있습니다.

지리적 지도에 묘사된 전형적인 지형은 선 특징(예: 도로), 면적 특징(카운티, 구획, 숲, 호수 등) 및 점 특징(마을, 도시 등)이다.지도의 특징을 지리적으로 정확하게 묘사할 뿐만 아니라, 독자가 어떤 이름이 어떤 특징을 묘사하는지 즉시 알 수 있도록 이러한 특징을 식별하는 이름을 배치하는 것이 매우 중요합니다.

자동 텍스트 배치는 지도 제작 및 지리정보시스템(GIS)에서 가장 어렵고 복잡하고 시간이 많이 걸리는 문제 중 하나입니다.다른 종류의 컴퓨터 그래픽스(차트, 그래프 등)는 엔지니어링 도면은 말할 것도 없고 라벨의 적절한 배치와 스프레드시트(Microsoft Excel 등)나 컴퓨터 소프트웨어 프로그램(Mathematica 등)을 작성하는 프로페셔널 프로그램도 필요합니다.

순진하게 배치된 라벨이 과도하게 겹쳐서 지도를 읽기 어렵거나 심지어 읽을 수 없게 됩니다.따라서 GIS는 각 라벨의 몇 가지 배치를 허용해야 하며 종종 라벨의 크기 조정, 회전 또는 제거(억제) 옵션도 허용해야 합니다.그런 다음 중복이 가장 적은 배치 세트를 선택하고 다른 바람직한 속성을 가집니다.가장 사소한 설정을 제외하고 문제는 NP-hard입니다.

규칙 기반 알고리즘

규칙 기반 알고리즘은 숙련된 인간 지도 제작자를 모방하려고 합니다.수세기에 걸쳐 지도 제작자들은 지도 제작과 라벨 배치 기술을 발전시켰다.예를 들어 경험이 많은 지도 제작자가 긴 도로의 도로 이름을 한 번 놓는 대신 여러 번 반복하거나, 해안과 매우 가까운 지점으로 묘사된 오션 시티의 경우, 지도 제작자는 "오션 시티"라는 레이블을 육지에 붙여 해안 ^[1]도시임을 강조합니다.

지도 제작자들은 ^[2]1962년 스위스 지도 제작자 에두아르 임호프가 항목별로 분류한 규칙과 규칙에 따라 작업합니다.예를 들어 뉴욕, 비엔나, 베를린, 파리 또는 도쿄는 우선순위가 높은 라벨이기 때문에 국가 지도에 표시되어야 합니다.이러한 라벨이 배치되면 지도 제작자는 주요 도로, 하천 및 기타 대도시와 같이 다음으로 중요한 라벨 클래스를 배치합니다.모든 단계에서 (1) 독자가 쉽게 특징과 관련지을 수 있도록 텍스트를 배치하고 (2) 라벨이 지도에 이미 배치된 것과 겹치지 않도록 한다.

로컬 최적화 알고리즘

가장 단순한 그리디 알고리즘은 맵 상의 연속된 라벨을 라벨의 오버랩을 최소한으로 억제하는 위치에 배치합니다.매우 간단한 문제에서도 결과는 완벽하지 않지만 매우 빠르다.

조금 더 복잡한 알고리즘은 배치 평가 기능의 로컬 최적화에 도달하기 위해 로컬 최적화에 의존합니다. 즉, 단일 라벨의 각 반복 배치가 다른 위치로 이동되며, 결과가 개선되면 이동이 유지됩니다.너무 촘촘하게 라벨이 붙어 있지 않은 맵에 대해서는 상당히 뛰어난 성능을 발휘합니다.조금 더 복잡한 변형에서는 동시에 두 개 이상의 레이블을 이동하려고 합니다.알고리즘은 로컬 최적치에 도달한 후에 종료됩니다.

심플한 알고리즘(시뮬레이트 어닐링)은 비교적 뛰어난 퍼포먼스로 좋은 결과를 가져옵니다.로컬 최적화와 같이 동작하지만 결과를 악화시키더라도 변경은 유지됩니다.이러한 변경을 유지할 가능성은 exp $\exp {\frac {-\Delta E}{T}}$ - $\exp {\frac {-\Delta E}{T}}$ E T $\exp {\frac {-\Delta E}{T}}$ \ $exp$ \ $frac$ { - \ $Delta$ E $\exp {\frac {-\Delta E}{T}}$ } 입니다. $T$ 여기서 $\Delta E$ E $(\displaystyle$ \ $Delta$ E $)$ 는 $\Delta E$ 평가 기능의 변화, $(\displaystyle$ T $)$ 는 $T$ 온도)애니링 일정에 따라 온도가 점차 낮아집니다.온도가 높으면 시뮬레이트된 어닐링이 라벨 배치를 거의 랜덤하게 변경하여 로컬 최적값을 벗어날 수 있습니다.나중에 매우 양호한 로컬 최적화가 발견되면 로컬 최적화와 유사한 방식으로 동작합니다.시뮬레이션 어닐링 솔루션을 개발하는 데 있어 주요 과제는 좋은 평가 기능과 좋은 어닐링 스케줄을 선택하는 것입니다.일반적으로 냉각 속도가 너무 빠르면 솔루션이 저하되고 냉각 속도가 너무 느리면 성능이 저하되지만, 일반적으로 스케줄은 여러 개의 파라미터로 이루어진 매우 복잡한 알고리즘입니다.

직접 검색 알고리즘의 또 다른 클래스는 다양한 진화 알고리즘(예: 유전 알고리즘)이다.

분할 및 정복 알고리즘

실제 지도에서 중요한 간단한 최적화는 라벨 세트를 독립적으로 해결할 수 있는 작은 세트로 나누는 것입니다.가능한 배치 중 하나에서 겹칠 수 있는 경우 두 레이블이 경쟁적입니다.이 관계의 전이적 폐쇄는 레이블 집합을 훨씬 더 작은 집합으로 분할할 수 있습니다.균일하고 촘촘하게 라벨이 표시된 지도에서는 일반적으로 단일 세트에 대부분의 라벨이 포함되며 라벨이 균일하지 않은 지도에서는 매우 큰 성능 편익을 가져올 수 있다.예를 들어, 세계 지도에 라벨을 붙일 때 미국은 유라시아 등과는 독립적으로 라벨을 붙인다.

2차 비교 알고리즘

지도 라벨링 문제를 나머지 라벨이 배치될 수 있는 위치가 2개뿐인 상황으로 줄일 수 있는 경우, 2가지 만족도의 인스턴스를 사용하여 배치의 모순을 회피함으로써 효율적으로 해결할 수 있습니다.즉, mo를 위한 정확하고 대략적인 라벨 배치 알고리즘입니다.복잡한 유형의 문제는 이 ^[3]원칙에 기초한다.

기타 알고리즘

자동 라벨 배치 알고리즘에서는 임의의 알고리즘을 사용하여 잠재적 라벨 집합에서 최대 분리 세트를 찾을 수 있습니다.다양한 그래프 솔루션, 정수 프로그래밍 등 다른 알고리즘도 사용할 수 있습니다.

메모들

^ Slocum, Terry (2010). Thematic Cartography and Geovisualization. Upper Saddle River, NJ: Pearson. p. 576. ISBN 978-0-13-801006-5.
^ Imhof, Eduard, "Die Anordnung der Namen in der Carte", Annuire International de Cartographie II, Orel-Füsli Verlag, Zürich, 93-129, 1962.영어 번역: "지도상의 이름 위치", 미국 지도 제작자, V.2 #2(1975), 페이지 128-144
^ Doddi, Srinivas, Marathe 교육 V;Mirzaian, 앤디, Moret, 버나드 M.E.;Zhu, 빈하이(1997년),"지도 라벨링과 그것의 일반화", Proc.8일 ACM-SIAM Symp.이산화 알고리즘(SODA),를 대신하여 서명함. 148–157, 아이 에스비엔 9780898713909, Formann, M.;바그너, F(1991년),"응용 프로그램과 지도의 레터링에 대한 포장 문제", Proc.7일 ACMSymp.해석 기하학, pp. 281–288, Poon, 정 Keung, 주, 빈하이; 친 프랜시스(1998년),"한 직선 지도 라벨에 대한 다항 시간 해결책", 정보 처리 불능, 65(4):201–207, doi:10.1016(98)00002-7, 바그너, 프랭크, 볼프, 알렉산더(1997년),"실용적인 지도 알고리즘 표지", 해석 기하학:.이론과 응용 프로그램, 7(5–6):387–404, doi:10.1016(96)00007-7.

레퍼런스

Freeman, H., 지도 데이터 처리 및 주석 문제, Proc. 제3회 스칸디나비아 회의.이미지 분석, Chartwell-Bratt Ltd.코펜하겐, 1983년
안, J, H. 프리먼, "자동 이름 배치 프로그램" Proc.AUTO-CARTO 6, 오타와, 1983. 444-455.
Freeman, H., "Computer Name Placement", 29장, 지리정보시스템, 1, D.J. Maguire, M.F. Goodchild 및 D.의 "컴퓨터 이름 배치"W. Rind, John Wiley, 뉴욕, 1991, 449-460.
Podolskaya N. N. 대화형 그래픽 애플리케이션을 위한 자동 레이블 충돌 제거 알고리즘.정보 테크놀로지 (ISSN 1684-6400), 9, 2007, 페이지 45~50.In Russian: Подольская Н.Н. Алгоритмы автоматического отброса формуляров для интерак тивных графических приложений.иоо 9 9 9 9 9 9, 9, 2007, 45-50
가메다, T, K이마이, 2003년점 및 원곡선에 대한 레이블 배치를 매핑합니다.IEICE 전자통신 및 컴퓨터 과학의 기초 거래.E86A(4): 835–840
리베이로 글레이드스턴과 루이스 로레나, 2006년.지도 레이블 배치 문제에 대한 휴리스틱스.컴퓨터와 지구과학.32:739–748.
바그너, F., A. 울프, V. 카푸어, T.스트라이크2001. 라벨의 적절한 배치를 위해서는 3가지 규칙으로 충분합니다.알고리즘.30:334–349.

외부 링크

[1] Slocum, Terry (2010). Thematic Cartography and Geovisualization. Upper Saddle River, NJ: Pearson. p. 576. ISBN 978-0-13-801006-5.

[imhof-2] Imhof, Eduard, "Die Anordnung der Namen in der Carte", Annuire International de Cartographie II, Orel-Füsli Verlag, Zürich, 93-129, 1962.영어 번역: "지도상의 이름 위치", 미국 지도 제작자, V.2 #2(1975), 페이지 128-144

[3] Doddi, Srinivas, Marathe 교육 V;Mirzaian, 앤디, Moret, 버나드 M.E.;Zhu, 빈하이(1997년),"지도 라벨링과 그것의 일반화", Proc.8일 ACM-SIAM Symp.이산화 알고리즘(SODA),를 대신하여 서명함. 148–157, 아이 에스비엔 9780898713909, Formann, M.;바그너, F(1991년),"응용 프로그램과 지도의 레터링에 대한 포장 문제", Proc.7일 ACMSymp.해석 기하학, pp. 281–288, Poon, 정 Keung, 주, 빈하이; 친 프랜시스(1998년),"한 직선 지도 라벨에 대한 다항 시간 해결책", 정보 처리 불능, 65(4):201–207, doi:10.1016(98)00002-7, 바그너, 프랭크, 볼프, 알렉산더(1997년),"실용적인 지도 알고리즘 표지", 해석 기하학:.이론과 응용 프로그램, 7(5–6):387–404, doi:10.1016(96)00007-7.

[1]

[2]

[3]

Search