제가 이미지 파일을 받아서
해당 이미지 파일에 있는 픽셀을 특정 컬러 테이블에 있는 값들이랑 비교해서
그 색에 가장 가까운 색(RGB를 3차원 공간으로 보고 공간의 거리 계산식 적용)으로 이미지를 바꾸는 프로그램을 만들건데요
만약에 이미지에 있는 픽셀이 n개고 테이블에 있는 픽셀이 m개면 시간복잡도는 O(mn) 이하로 못 줄어드는 건가요?
해당 이미지 파일에 있는 픽셀을 특정 컬러 테이블에 있는 값들이랑 비교해서
그 색에 가장 가까운 색(RGB를 3차원 공간으로 보고 공간의 거리 계산식 적용)으로 이미지를 바꾸는 프로그램을 만들건데요
만약에 이미지에 있는 픽셀이 n개고 테이블에 있는 픽셀이 m개면 시간복잡도는 O(mn) 이하로 못 줄어드는 건가요?
초보라 잘 모르겠네요... 통계학과라 변형시키는방법도 잘 모르겠고..
O(n)아닌가요? 위치의존해싱쓰면
써본적이 없으니 카더라밖에.. 죄송함다 ㅜ
이거 공간에서 가장 가까운 점 찾는 알고리즘 같은거 있는데 그거 쓰면 좀더 빨라질꺼다. 근데 사진이 왠만큼 큰거 아니면 O(MN) 으로도 괜찮을 것 같은데 - dc App
https://en.m.wikipedia.org/wiki/Nearest_neighbor_search
참고 - dc App
꿀벌/ 이거 그렇게 쉽지 않음 - dc App
이거 N -> M 에서 맵핑하는 함수 만드는건 M이 불연속 공간이라서 쉽지 않음. 결국에는 탐색하는 알고리즘 써야됨 - dc App
이게 테이블이 규칙같은게 있는게 아니고 말그대로 테이블값을 입력하는거라 완전 무작위임...
메모이데이션을 해두면 좀 더 빨라질거 같애. 같은 값을 갖는 픽셀이 여러개 있을 수도 있으니 - dc App
RGB값으로 정렬해보는거도 생각해봤는데 어찌됐든간에 r g b 값 각각에 대해 차 구해서 제곱한다음 더해서 3루트씌우고 해야되는건 매한가지라...
그니까 Nearest Neighbor Search 문제라고 ㅇㅇ 내가 준 링크 보렴 - dc App
메모이제이션 해봤는데 시간이 더 늘어나더라구요 이미지자체가 실제사진이거나 그러면 중복되는 값이 거의 없어서
ㅇㅇ/ 그렇게 하면 대신 루트 씌워서 탐색해야되는 범위는 더 좁힐 수 있지. 물론 더 좋은 방법은 많다 - dc App
한번 볼게요 감사합니다