탐색 알고리즘 질문 입니다.
글쓴이: wodnrrns / 작성시간: 화, 2009/02/10 - 1:56오후
안녕하세요 제가 일하다가 갑자기 막히는게 있어서요.
첨부한 사진과같은 블럭들이 있는데요.
탐색의 시작점은 주황색 위치 입니다. 중앙에서 탐색을 시작해서 흰색 구간들을
체크하고 싶습니다. 값으로는 흰색과 하늘색 구간이 같은 값을 가지고 있습니다.
어두운 노란색을 경계로 흰색 부분만 선택하고 싶을때 어떤 방법의 탐색이있을까요?
정리하자면 꼭 사진과 같은 모양은 아니고 중앙과 같은 값을 가지는 연결된 녀석들을 선택할 수 있는
방법이 무었이 있을지 조그만 의견이라도 주시면 정말 감사하게 받겠습니다.
File attachments:
| 첨부 | 파일 크기 |
|---|---|
 aa.jpg | 27.68 KB |
Forums:
간단히는; 전체 맵
간단히는;
전체 맵 크기가 큰게 아니라면 BFS를 하면 될것 같습니다.
Queue에 주황점을 넣고 시작하면 될듯하고요.
Queue에서 하나 꺼내서 하얀색이면 OK체크하고
그 주변점들을 Queue에 넣고, 하는 식으로 하면 될듯요.
다만, 이미 방문한 곳들을 표시해주어야 중복하지 않게 될겁니다.
답변 감사드려요.
우선 답변해주셔서 감사드립니다.
맵 크기는 11 x 11로 더 작아지기는 하겠지만 더 커지지는 않을것 같은데요.
실시간 시스템에서 칩으로 나올거라서 메모리 부분에 제약이 많아서요.
복잡도는 어느정도 감안하고라도 큐와 같은 형태로는 힘들것 같네요.
BFS방법을 이야기 듣고 생각을 해 보았는데요, 코딩적으로는 가능할거라 생각이 들지만
메모리 사용양이 너무 많이지지 않을까요?
아직은 고민중이네요. 정 않되면 우선은 말씀해 주신 방법으로 구현해 봐야겠습니다.
다시한번 감사드립니다.
전형적인 그래픽스의
전형적인 그래픽스의 rasterization filling 알고리즘 상황같군요. 논문이 꽤 많이 있습니다. 그래픽스쪽 논문들을 참고하세요. 단 하드웨어 구현시 특허문제를 아주 세밀히 잘 살피셔야 합니다. ( 정말 주의를 요합니다. )
반드시 closed 되지 않은 영역까지 포함되는 문제일경우엔 위에분 처럼 queue 이용 외에 좋은 알고리즘은 없을 듯 합니다.
다만 큐 사이즈를 줄이고 싶으시다면, 중앙점을 기준으로 상하좌우로 뻗어나가며 색칠하는 방식의 알고리즘을 선택하시면 꽤 큐 사이즈가 줄어들 것입니다.
( 중앙점을 기준으로 상하좌우로 뻗으며 어두운 노란색을 만나기 전까지의 흰색점은 모두 내부 영역으로 처리하시면 되겠습니다. 또한 어두운 노란색 이후로 만나는 점은 우선 판별하지 마시고 어둔 노란색을 만날때까지만 뻗어나가시면 됩니다. 이 처리가 끝난뒤에 각 대각선위치의 점들을 큐잉해서 다시 같은 행동을 반복합니다. 내부영역으로 이미 처리된 점은 skip 잘 하시고요. )
아예 큐를 사용하지 않는 알고리즘도 있습니다. 다만 제약 조건이 따릅니다.
1. 반드시 원점을 포함한 영역은 닫힌공간일것 ( 다만 이 경우 외부에 강제로 테두리를 어두운 노란색으로 만들어 줄 수 있겠죠 따라서 꼭 제약은 아닙니다. )
2. 닫힌공간은 반드시 11 by 11 영역에 1개만 존재할것. ( 2개 이상 존재할경우엔 굉장히 복잡해 집니다. 거의 불가능 해지지요. )
이러한 가정하에서는 라인 단위로 훑어가며 어두운 황색을 만나면 변수를 1씩 더해가며 버퍼를 채워나가다가 다 버퍼를 채우면,
원래 있던 주황색자리점의 버퍼값을 꺼내봐서
버퍼값이 홀수면 -> 모든 홀수점이 영역
버퍼값이 짝수면 -> 모든 짝수점이 영역
인 알고리즘도 있습니다. 11 by 11 ( 혹은 테두리 포함 13 by 13 ) 의 계산시간이면 무조건 끝나게 되겠지요.
-- 주신 그림을 보니 아래 알고리즘은 사용이 불가능하겠네요. 테두리를 강제로 만들고 거기의 색깔을 무언가 다른걸로 채운뒤 알고리즘을 다시 고민해보시면 혹시 방법이 있을지도 모르겠습니다만...
Neogeo - Future is Now.
Neogeo - Future is Now.
성의있는 답변 감사 드립니다.
역시나 아직까지는 문제를 확실히 해결하지는 못하고 있지만 알려주신 덕분에 그럭저럭
방향이 보이는것 같네요. 하드웨어 구성 때문에 복잡도를 최대한 줄일려고 하였는데 그렇게는 힘들것 같네요.
큐를 사용하여 BFS방법으로 만들어 두긴 하였지만 하드웨어 팀과 이야기해서 수정이 있을것 같아요.
상당히 자세하고 꼼꼼한 답변 주셔서 감사 드립니다.
역시 이곳분들이 우리나라 IT를 이끌어가는 분들 같습니다.
늘 좋은일만 있으시고 늦었지만 새해 복 많이받으세요.
와... 이거 재미있는
와... 이거 재미있는 brain teaser로군요.
neogeo님 글을 보니 옛날에 flood fill 생각이 납니다.
보다 재미있게 이렇게 풀어보면 어떨까요?
먼저 윤곽선을 추출합니다. 예를 들어 원본데이터가 다음과 같다면.. (#가 주황색 점 입니다.)
000000000000
000000000000
000001100000
000010010000
00010#001000
000010010000
000001100000
000000000000
100000000001
010000000010
001000000100
#로부터 출발해서 1이라는 값만 쉽게 따라갈 수 있습니다.
그래서 결국 원하는 윤곽선만 X로 바꾸면 이렇게 바꿀 수 있겠죠
(#에서 상하좌우 아무쪽이던 출발 -> 시계 혹은 반시계 방향으로, 막히면 다음 1을 찾음)
000000000000
000000000000
00000XX00000
0000X00X0000
000X0#00X000
0000X00X0000
00000XX00000
000000000000
100000000001
010000000010
001000000100
자 그러면 위의 그림에서, 데이터를 X축 Y축으로 구분해서 볼 때
우리가 도출한 윤곽선을 다항식이라고 생각하면
---> x 축
|
|
V
y축
우리가 원하는 0 값은
y축 처음부터 x축에 존재하는 X, 즉 교차점
두 X 사이에 존재하는 것이 됩니다.
보다 상황을 복잡하게 해서 우리가 취급하는 형태가 아메바 같은 형태라고 하더라도
결국은 마찬가지가 되겠군요.
윤곽 데이터를 저장할 수 있는 저장공간이 있다면, 나중에 둘레 길이 측정도 할 수 있겠네요.
원글의 제약조건에는 부합하지 않는 내용이었나요?
얼마 전에 kldp의 Haskell관련 글을 읽고 호기심으로 조금 봤는데,
모나드가 골치 아팠지만 재밌는 랭귀지였습니다.
이문제를 Haskell로도 풀 수 있지 않을까 생각이 드네요..
아.. 이러다 잠 못자면 어떡하지?
-------------------------------------------------
$yes 4 8 15 16 23 42
-------------------------------------------------
$yes 4 8 15 16 23 42
답변 감사드립니다.
답변 감사드립니다.
하지만 문제의 내부모양이 정적이 아니기 때문에 위의 그림에서는 해결 가능하지만
가령 내부 모양이 M 자와 같은 형태일때는 다각형의 외부를 구한다고해도 왼쪽의 x 좌표와 오른쪽의 x좌표 사이에
0들이 위치한다고 단언할 수 없을것 같습니다.
아메바 같은형태를 이야기 하셨지만 역시나 초승달 모양의 아메바일경우에는 (U자모양) 역시나 위의 문제에
봉착하게 되는것이죠.
물론 이는 스켄라인 채우기와같은 방법으로 해결할 수도 있지만 세그멘테이션과 같은 과정을 또 거쳐야할것 같구요.
역시나 채우기문제는 위에 말씀해주신것과같이 범람채우기나 BFS를 이용한 탐색이 정석인것 같습니다.
우선은 재귀와 큐를 이용한 두가지 방법 모두 구현은 해놓았지만 아직 마음에 들진 않아서 더 고민중입니다.
성의것 해주신 답변 감사드립니다.
무슨 말씀인지
무슨 말씀인지 알겠습니다.
그것도 이런 방법이 있을 것 같군요,.
W자형 그래프가 특정 y절편에 교차할 경우 가장 판단이 쉬운 경우는
다음과 같겠죠
--x--x--x--x--
이것은 W의 하단 1/4 부분에 해당하는 가장 쉬운 부분이 되겠군요.
우리가 원하는 데이터 영역은 첫째와 둘째, 그리고 셋째와 넷째의 x의 사이에 있는 것들이라고
판단 가능합니다.
문제는 중간
--x---x----x---
혹은 하단
---x-----x-----
등과 같은 경우겠죠
......
하지만 위의 경우 중간의 경우도 가운데 x는 두 선이 하나로 처리된것으로 할 수 있습니다.
--x---xx---x---
이러한 부가적인 판단은 폐곡선의 경우 여러 방법을 동원할 수 있지 않을까요?
외곽선 추출시 이미 폐곡선의 외부와 내부는 구분이 가능하니까
.
.
.
외곽선을 마킹하면서 단순한 X외에 다른 플래그들로 마크를 해주고 (플래그의 종류가 늘어나는군요)
다시 y축으로 스캔을 해 가면서 우리가 고려할 마크들의 관계를 고려해 주면
보다 좋은 결과를 도출할 수 있을 것 같습니다.
사실, 전에 직장에서 스캔한 만화 이미지를 각 cut별로 나누어 저장하는
알고리즘을 함께 해 본적이 있습니다. PC환경이고 time critical한것이 아니었기때문에
기본적으로는 위에서도 언급된 알고리즘과 유사하게
"재귀적으로 여러쓰래드가 각자 길을 찾아가는" 식으로 출발했는데
비 정형화되고 폐곡선이 아닌경우가 발생하는 만화의 cut을 분리하는 것은 flood fill과는 다른 관점이 필요하더군요
저는 중간에 나왔지만, 남은 친구들은 유전알고리즘으로 best case들을 수집하는
쪽으로 작업을 계속 했구요..
그런데, 저 처음의 단순한 알고리즘으로도 어느정도는 만족할 만한 결과가 나왔던 것 같네요.
음.. 아무튼 덕분에 오랜만에 뭔가 건설적인 고민을 할 수 있어서 즐거웠습니다.
-------------------------------------------------
$yes 4 8 15 16 23 42
-------------------------------------------------
$yes 4 8 15 16 23 42
좋은 이야기 감사드립니다.
좋은 이야기 감사드립니다.
만약 지금하고있는 부분에서 문제가 생긴다면 말씀해주신 방법을
응용하여 라인별로 처리하는것이 제일 합당해 보이네요.
조언 감사드리고 늘 좋은일만 가득하시길 빌겠습니다..
에구에구 무슨
에구에구 무슨 말씀을요
제가 감사드립니다.
좋은 결과를 기원드립니다~
-------------------------------------------------
$yes 4 8 15 16 23 42
-------------------------------------------------
$yes 4 8 15 16 23 42
지뢰찾기 알고리즘이랑 같을까요 ^^;
저는 recursive함수로 구현했었는데요.. 메모리 사용량이 많아지려나요
지뢰찾기와 유사하기도 합니다.
유사한 형태라는건 사실이지만 주변의 지뢰의 개수( 위의 그림에서는 갈색 벽이되겠죠.) 를 카운팅 하기위해서는
벌써 한번의 탐색이 이루어져야 하겠습니다. 복잡도로 이야기하자면 한 위치당 주변의 8블럭을 검사해야 하기때문에
11x11x8의 접근도를 가지는 검사겠구요.
그 후에도 역시나 내부를 채우기 위해서는 지뢰찾기 알고리즘을 병행해야 하기때문에 역시나
심플한 해결방법은 아닌것 같네요.
저역시 recursive함수로 구현을 해 놓고 있지만 저는 범람채우기 라는 알고리즘을 사용하였습니다.
물론 아마도 recursive가 아닌형태로 조만간 변경을 할것 같지만요...
recursive의 형태는 프로그램으로 돌릴경우 문맥교환 시간때문에 스택의 사용양이 많아질 수 있지만 무조건은 아닌걸로
알고있습니다. 메모리 역시 사용하는 분야에따라 달라지는 것이구요.
단지 제가 원하는 방향이 하드웨어쪽이라 칩으로 구현하기에 recursive는 타이밍 문제가 있어서 고민중입니다.
좋은의견 감사합니다. 지뢰찾기 알고리즘 쪽으로도 옵티마이즈가 가능할지 생각 해 보아야겠네요.
댓글 달기