javascript는 HTML과 CSS로 만들어진 웹페이지를 동적으로 변경해주는 언어. 경고창을 띄우고, 탭 인터페이스를 만들고, Drag & Drop 기능의 웹 에플리케이션을 만들수 있다.
예전에 Javascript는 원래 많이 인기없는 언어였다. 허나 구글이 지도 서비스를 내 놓자 HTML/CSS 만으로도 플래쉬와 같은 효과를 구현할 수 있다는 것을 증명. 거기에 ajax 열풍이 가세하면서 favascript의 중세는 끝이 난다. 자바스크립트의 재조명과 스티브 잡스의 플래쉬 혐오, HTML5의 등장이 맞물리면서 플래쉬의 입지가 빠르게 줄어들고 있고, 그 빈자리를 빠르게 자바스크립트가 대체하기 시작했다.
지금은 자바스크립트가 브라우저에서만 사용되는 언어에서 벗어나서 서버에서도 사용되고 (node.js) 데스크탑 에플리케이션 (adobe air)에서도 사용된다. 플래쉬 역시 그 안에서는 자바스크립트를 사용하고 있다.
자바스크립트는 기능이 별로 없는 언어이다. 그러면서도 프로그램이의 앙꼬에 해당하는 요소들 이를테면, 변수, 반복, 조건, 함수 심지어 객체까지 모두 가지고 있는 본격적인 프로그램이 언어이다.
1. 웹 브라우저 자바스크립트
순수한 자바스크립트 기술을 이용해서 웹 브라우저를 제어하는 방법에 대해 다루는 것이 간결한 방법이다. 하지만 오늘날 순수한 자바스크립트를 이용해서 웹 브라우저를 제어하는 방법은 잘 사용하지 않는다. 더 적은 코드로 더 강력한 효과를 얻을 수 있는 수단을 제공하는 각종 라이브러리를 사용하기 떄문이다.
만약 순수 자바스크립트 만으로 웹브라우저를 제어하는 것은 다소 현실성이 떨어질 것이고, 특정 라이브러리에 대해서만 공부한다면 해당 라이브러리가 제공하는 기능에 갇히게 될 것이다. 따라서 좀더 원론적으로 파보려고 한다.
DOM 이라는 것은 현재 직접 사용하지는 않는다. jquery, yui 등의 라이브러리를 이용해 간접적으로 간결하게 사용한다. 이러면 훨씬 더 적은 코드로 프로그램을 작성할 수 있다. 즉, 브라우저에서 기본적으로 제공하는 DOM이라는 가장 기본적인 개념을 알고 있어야 더 쉽고 간편하게 웹을 제어할 수 있다.
2. Javascript 로드하기
inline 방식
script 로드
외부파일에서 로드
참고로 가끔씩 script 를 head 에 위치하였는데 오류가 발생하는 경우가 두루 있다. 왜냐 스크립트를 가져오는 타이밍이 원하는 대로 일치하지 않기 때문이다. 이를 해결하기 위해
window.onload = function() { }
이라는 함수를 도입해 모든 element 에 대한 로드가 끝났을 때, 브라우저에 의해서 호출되는 함수를 사용해 오류 없이 안전하게 사용할 수 있다.
허나 script 파일은 head 태그보다 페이지의 하단에 위치시키는 것이 더 좋은 방법이다.
3. Object 모델
생활코딩 출처
웹 브라우저의 구성요소들은 하나하나가 객체화 되어 있다. 자바스크립트로 이 객체를 제어해서 웹 브라우저를 제어할 수 있게 되는 것이다. 해당 객체들은 그림과 같이 서로 계층적인 관계로 구조화되어 있다.
BOM 과 DOM 은 이 구조를 구성하고 있는 가장 큰 틀의 분류라고 할 수 있다.
BOM 은 웹페이지의 내용을 제외한 브라우저의 각종 요소들을 객체화시킨 것이다. 전역객체 window 의 프로퍼티에 속한 객체들이 이에 속한다.
DOM 은 웹페이지의 내용을 제어한다. document 객체가 이러한 작업을 담당한다. 뒤에서 알아보겠지만 특정한 선택자를 뽑아낼 수도 있고, 속성 값을 변경할 수도 있다.
4. BOM
BOM(Browser OBject Model) 이란 웹 브라우저의 창이나 프레임을 추상화해서 프로그래밍적으로 제어할 수 있또록 제공하는 수단이자 객체를 말한다.
BOM 은 전역객체인 Window 의 프로퍼티와 메소드들을 통해서 제어할 수 있다. 따라서 BOM 에 대한 공부는 window 객체의 프로퍼티와 메소드의 사용법에 대해 공부하는 거라 봐도 된다.
그러면 window 객체의 사용법에 대해 알아보자.
① 전역객체 window
거의 모든 객체들이 소속되어있는 window 객체로써 전역객체라고도 불린다. 즉, 전역객체이면서 창이나 프레임을 의미한다고 볼 수 있다.
window 객체는 식별자 window 를 통해서 얻을 수 있다. 또한 생략 가능하다. window 객체의 메소드인 alert 를 호출하는 방법은 위와 같다. 여튼, 우리가 쓰는 거의 모든 메소드들은 window 에 속한다고 볼 수 있다.
<!DOCTYPE html>
<html>
<script>
var a = 1;
alert(a);
alert(window.a);
</script>
<body>
</body>
</html>
이러한 예제를 통해서 알 수 있는 것은 전역변수와 함수가 사실은 window 객체의 프로퍼티와 메소드라는 것이다. 또한 모든 객체는 사실 window의 자식이라는 것도 알 수 있다. 이러한 특성을 ECMAScript에서는 Global 객체라고 부른다. ECMAScript의 Global 객체는 호스트 환경에 따라서 이름이 다르고 하는 역할이 조금씩 다르다. 웹 브라우저 자바스크립트에서 window 객체는 ECMAScript의 전역객체이면서 동시에 웹브 라우저의 창이나 프레임을 제어하는 역할을 한다.
② 사용자와 커뮤니케이션 하기
HTML은 form을 통해서 사용자와 커뮤니케이션할 수 있는 기능을 제공한다. 자바스크립트에는 사용자와 정보를 주고 받을 수 있는 간편한 수단을 제공한다.
alertalert는 경고창이라고도 부르며 사용자에게 정보를 제공하거나 디버깅등의 용도로 많이 사용한다. 현재는 디버깅용도로 console.log 를 많이 사용한다.
confirmconfirm 역시 alert와 비슷한 기능을 하지만 확인을 누르면 true를 반환하고, 취소를 누르면 false를 반환한다는 점을 기억하자. 이걸로 또 상호 작용할 수 있으니까.
promptprompt 역시 경고창이 뜨는 건데 이거는 사용자로부터 입력을 받아서 그 값을 반환하는 것이다. 이 때 입력값이 없으면 null 을 반환하니 이걸 이용해서 또 코딩할 수 있을 것이다.
③ Location 객체
location 객체는 문서의 주소와 관련된 객체로 window 객체의 프로퍼티다. 이 객체를 이용해서 윈도우의 문서 URL을 변경할 수 있고, 문서의 위치와 관련해서 다양한 정보를 얻을 수 있다. 이 때 URL을 변경할 수 있다는 점을 잘 기억하자.
console.log(location.toString(), location.href);
이것은 현재 윈도우의 문서가 위치하는 URL을 알아내는 방법이다. 둘 다 비슷한 반환 값이라 어느 것을 쓰든 상관없다.
참고로 alert같은 경우는 인자로 들어오는 값은 무조건 문자열이기 때문에 객체를 인자로 넣어도 toString()으로 출력되기 때문에 loaction 을 인자로 넣으면 url을 반환하여 출력한다.
이 세상에는 아주 많은 브라우저들이 있다. 크롬, 인터넷, 파이어폭스 등등 이 들의 동작 방법은 w3c 에서의 ECMA 스펙에 따라 브라우저를 만든다. 때문에 스펙에 맞는 부분은 비슷하지만 스펙에 없는 분야는 다르게 코딩한다. 때문에 때에 따라 브라우저의 호환성을 확인해야 한다. 이런 문제를 크로스 브라우징이라고 한다.
참고로 처음으로 상용화된 성공적인 브라우저는 넷스케이프였다. 이 때 도입된 언어가 자바스크립트이다. 이 때 마이크로소프트가 ie를 만들어 브라우저 전쟁에 뛰어든다. 이 때 자바스크립트의 메소드 명칭이 서로 달라지게 되는 등 여러 불편함이 생기게 되었고, 그에 따라 웹 표준이 생겼다. 즉, 웹 표준대로 메소드 명을 통일 화 하고, 동일한 API 를 사용하도록 하였다. 때문에 이 기능을 좀 더 효율적으로 사용하는 방법으로 전쟁 방향이 바뀌게 되었다.
console.dir(navigator);
이 명령어를 통해 navigator의 모든 객체 프로퍼티를 열람할 수 있다.
appName ex) navigator.appName
웹브라우저의 이름이다. IE는 마이크로소프트 인터넷 익스플로러, 파이어폭스 크롬등은 nescape로 표시된다.
appVersion ex) navigator.appVersion
브라우저의 버전을 의미한다.
userAgent ex) navigator.userAgent
브라우저가 서버 측으로 전송하는 USER-AGENT HTTP 헤더의 내용이다.
platform 브라우저가 동작하고 있는 운영체제에 대한 정보다.
※ 기능 테스트
Navigator 객체는 브라우저 호환성을 위해서 주로 사용하지만 모든 브라우저에 대응하는 것은 쉬운 일이 아니므로 아래와 같이 기능 테스트를 사용하는 것이 더 선호되는 방법이다. 예를 들어 object.keys라는 메소드는 객체의 key 값을 배열로 리턴하는 object의 메소드다. 이 메소드는 ECMAScirpt5에 추가되었기 때문에 오래된 자바스크립트와는 호환되지 않는다. 아래의 코드를 통해서 호환성을 맞출 수 잇다.
if (!Object.keys) {
Object.keys = (function () {
'use strict';
var hasOwnProperty = Object.prototype.hasOwnProperty,
hasDontEnumBug = !({toString: null}).propertyIsEnumerable('toString'),
dontEnums = [
'toString',
'toLocaleString',
'valueOf',
'hasOwnProperty',
'isPrototypeOf',
'propertyIsEnumerable',
'constructor'
],
dontEnumsLength = dontEnums.length;
return function (obj) {
if (typeof obj !== 'object' && (typeof obj !== 'function' || obj === null)) {
throw new TypeError('Object.keys called on non-object');
}
var result = [], prop, i;
for (prop in obj) {
if (hasOwnProperty.call(obj, prop)) {
result.push(prop);
}
}
if (hasDontEnumBug) {
for (i = 0; i < dontEnumsLength; i++) {
if (hasOwnProperty.call(obj, dontEnums[i])) {
result.push(dontEnums[i]);
}
}
}
return result;
};
}());
}
⑤ 창 제어
window.open 메소드는 새 창을 생성한다. 현대의 브라우저는 대부분 탭을 지원하기 떄문에 window.open 은 새 창을 만든다. 메소드 사용법은 다음과 같다.
→ 2번째 인자의 종류
_self : 현재 창에서 실행
_blank : 새 창에서 실행
ot : 이름을 붙여서 실행
→ 세번째 인자 : 그냥 모양에 관련된 (style)
<!DOCTYPE html>
<html>
<style>li {padding:10px; list-style: none}</style>
<body>
<ul>
<li>
첫번째 인자는 새 창에 로드할 문서의 URL이다. 인자를 생략하면 이름이 붙지 않은 새 창이 만들어진다.<br />
<input type="button" onclick="open1()" value="window.open('demo2.html');" />
</li>
<li>
두번째 인자는 새 창의 이름이다. _self는 스크립트가 실행되는 창을 의미한다.<br />
<input type="button" onclick="open2()" value="window.open('demo2.html', '_self');" />
</li>
<li>
_blank는 새 창을 의미한다. <br />
<input type="button" onclick="open3()" value="window.open('demo2.html', '_blank');" />
</li>
<li>
창에 이름을 붙일 수 있다. open을 재실행 했을 때 동일한 이름의 창이 있다면 그곳으로 문서가 로드된다.<br />
<input type="button" onclick="open4()" value="window.open('demo2.html', 'ot');" />
</li>
<li>
세번재 인자는 새 창의 모양과 관련된 속성이 온다.<br />
<input type="button" onclick="open5()" value="window.open('demo2.html', '_blank', 'width=200, height=200, resizable=yes');" />
</li>
</ul>
<script>
function open1(){
window.open('demo2.html');
}
function open2(){
window.open('demo2.html', '_self');
}
function open3(){
window.open('demo2.html', '_blank');
}
function open4(){
window.open('demo2.html', 'ot');
}
function open5(){
window.open('demo2.html', '_blank', 'width=200, height=200, resizable=no');
}
</script>
</body>
</html>
웹사이트가 가지고 있는 기능이 우리의 브라우저를 제어할 수 있게 되면 그것이 바로 보안 취약점이다. 때문에 브라우저에서 어떤 스크립트를 실행되게 할 지 설정할 수 있다. 같은 도메인에 있는 서버와 사용자라면 자유자재로 값을 변경할 수 있지만 다른 도메인인 경우 원격하는 데에 제한이 생긴다 이것을 팝업 차단이라고 한다.
즉 window.open 은 팝업 차단에 걸릴 수 있다는 것을 기억하자.
5. DOM
웹 페이지를 자바스크립트로 제어하기 위한 객체 모델을 의미한다. window 객체의 document 프로퍼티를 통해서 사용할 수 있다. window 객체가 창을 의미한다면 document 객체는 윈도우에 로드된 문서를 의미한다고 할 수 있다.
5.1. 제어 대상 찾기
문서를 자바스크립트로 제어하려면 제어의 대상에 해당되는 객체를 찾는 것이 제일 먼저 할 일이다. 문서 내에서 객체를 찾는 방법은 document 객체의 메소드를 이용한다.
document.getElementsByTagName
document.getElementsByClassName
document.getElementById
document.querySelector
document.querySelectorAll
5.2. Jquery
현재 많은 사람들이 사용하는 자바스크립트 라이브러리 이다. 이것을 이용해서 훨씬 쉽게 원하는 태그나 DOM을 조회하고 검색할 수 있다. 즉, 웹페이지를 쉽게 조작할 수 있도록 돕는 도구이다. jquery를 사용하기 위해서는 jQuery를 HTML로 로드해야 한다. 아래는 jQuery를 로드하는 방법이다.
이를 통해서 알 수 있는 것은 엘리먼트의 종류에 따라서 리턴되는 객체가 조금씩 다르다는 것이다.
＊DOM Tree
모든 엘리먼트는 HTMLElement의 자식이다. 따라서 HTMLElement의 프로퍼티를 똑같이 가지고 있다. 동시에 엘리먼트의 성격에 따라서 자신만의 프로퍼티를 가지고 있는데 이것은 엘리먼트의 성격에 따라서 달라진다. HTMLElement는 Element의 자식이고 Element는 Node의 자식이다. Node는 Object의 자식이다. 이러한 관계를 DOM tree 라고 한다.
이 관계를 그림으로 나타내면 아래와 같다.
이러한 관계를 이해하지 못하면 필요한 API를 찾아내는 것이 어렵거나 몹시 혼란스러울 것이다. 다행인 것은 jQuery와 같은 라이브러리를 이용한다면 이러한 관계를 몰라도 된다.
＊HTMLCollection
HTMLCollection 은 리턴결과가 복수인 경우에 사용하게 되는 객체다. 유사배열로 배열과 비슷한 사용방법을 가지고 있지만 배열은 아니다.
<!DOCTYPE html>
<html>
<body>
<ul>
<li>HTML</li>
<li>CSS</li>
<li id="active">JavaScript</li>
</ul>
<script>
console.group('before');
var lis = document.getElementsByTagName('li');
for(var i = 0; i < lis.length; i++){
console.log(lis[i]);
}
console.groupEnd();
console.group('after');
lis[1].parentNode.removeChild(lis[1]);
for(var i = 0; i < lis.length; i++){
console.log(lis[i]);
}
console.groupEnd();
</script>
</body>
</html>
이 복수형은 특이점이 있는데 바로 목록이 실시간으로 변경된다는 것이다. 즉, 태그를 추가하거나 변경하는 경우 이 유사배열 내의 값도 달라진다.
cf) console.group 은 그룹 별로 콘솔에 띄워주는 매소드이다. 예를 들어 group('before') 이라고 치면 해당 before 트리가 생긴다. 즉 위의 코드를 실행시키면 다음과 같이 된다
이 그룹을 끝내고 싶으면 console.groupEnd() 를 호출하면 된다.
5.4. Element 객체
element 객체는 엘리먼트를 추상화한 객체다. HTMLElement 객체와의 관계를 이해하기 위해서는 DOM의 취지에 대한 이해가 선행되야 한다.
DOM은 HTML만을 제어하기 위한 모델이 아니다. HTML이나 XML, SVG, XUL 과 같이 마크업 형태의 언어를 제어하기 위한 규격이기 때문에 Element는 마크업 언어의 일반적인 규격에 대한 속성을 정의하고 있고, 각각의 구체적인 언어를 위한 기능은 HTMLElement, SVGElement, XULElement와 같은 객체를 통해서 추가해서 사용하고 있다.
＊다른 객체들과의 관계
DOM의 계층구조에서 Element 객체의 위치는 아래와 같다.
이 때 왜 굳이 Element 와 HTMLElement 를 나누었을까?
마크업 언어를 제어하기 위한 규격이 DOM 이라, 다른 말로 DOM 표준은 HTML, XML, SVG, XUL 등등의 마크업 들을 제어하기 위한 표준이라 할 수 있기 때문에 모든 Element 들의 기능들을 제어하기 위해 Element 객체를 따로 두었다.
예를 들어 style 이라는 프로퍼티는 Element에는 없고 HTMLElement 에 있는 프로퍼티이다. (다른 언어는 필요 없을 수 있기 때문에)
상세한 프로퍼티는 개발자 도구에 들어가서 확인할 수 있다. 밑으로 갈수록 상속 관계이니 직접 확인해보자.
＊주요 기능
1) 식별자
문서 내에서 특정한 엘리먼트를 식별하기 위한 용도로 사용되는 API
엘리먼트를 제어하기 위해서는 그 엘리먼트를 조회하기 위한 식별자가 필요하다. HTML에서 엘리먼트의 이름과 id 그리고 class 는 식별자로 사용된다. 식별자 API는 이 식별자를 가져오고 변경하는 역할을 한다.
재귀적 호출에 대한 개념을 먼저 잡고 넘어가자. 그 이유는 완전 탐색 시에, 해당 호출 방식을 자주 활용하기 때문이다.
재귀함수의 기본적인 이해
재귀함수란: 함수 내에서 자기 자신을 다시 호출하는 함수
: 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수
재귀함수 호출방식
void RecursiveFunction(void) {
printf("Recursive function example1 \n");
RecursiveFunction();
}
※ 기저 사례 (base case)
▷ 더 이상 쪼개지지 않는 가장 작은 작업, 즉 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문에 포함될 내용 ▷ 기저 사례를 선택할 때는 존재하는 모든 입력이 항상 기저 사례의 답을 이용해 계산될 수 있도록 신경써야 한다.
＃ 완전탐색(exhaustive search)
① 완전탐색이란?
▷ '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게
가능한 방법을 전부 만들어 보는 알고리즘
을 뜻한다. ▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다. ▷ (예제) n개의 원소 중 m개를 고르는 모든 조합을 출력하는 코드
// n : 전체 원수의 수
// picked : 지금까지 고른 원소들의 번호
// toPick : 더 고를 원소의 수
// 일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다.
void pick(int n, vector<int>& picked, int toPick) {
// 기저 사례 : 더 고를 원소가 없을 때 고른 원소들을 출력한다.
if(toPick == 0) {
printPicked(picked);
return;
}
// 고를 수 있는 가장 작은 번호를 계산한다.
int smallest = picked.empty() ? 0 : picked.back() + 1;
// 이 단계에서 원소 하나를 고른다.
for(int next = smallest; next < n; ++next) {
picked.push_back(next);
pick(n, picked, toPick - 1);
picked.pop_back();
}
}
② 완전 탐색 방법
Brute Force for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
비트마스크: 거두절미 하고 이야기 하면, 비트마스크는 알고리즘 이라기 보단 테크닉에 가깝습니다. 비트는 컴퓨터에서 다루는 최소 단위이며, 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술을 비트마스크 라고 한다.
순열 순열의 시간 복잡도는 O(N!)으로 백트래킹과 비슷하다. check 배열 하나 두고 들어갔다가 나오고, 들어갔다가 나오는 방식을 구현한다. 예시는 밑에 추가해놨으니 참고해보자.
백트래킹(DFS): 백트래킹은 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때 만이다. 모든 경우의 수를 모두 찾는 것보다 ‘경우에 따라' 훨씬 빠를 수 있다. 왜냐하면 조건이 만족하는 경우라는 조건이 있기 때문이다.한 컬럼에 Queen을 두었으면 오른쪽 컬럼에 가능한 자리에 Queen을 둔다. 또 다시 오른쪽 컬럼 중에서 가능한 자리에 Queen을 둔다. 이 과정을 반복한다. 만약에 N개의 Queen을 두었다면 카운트를 증가 시킨다. 이제부터가 중요한데, 성공하기 직전으로 상태를 되돌린다(back). 그리고 N번째 컬럼 중 다른 칸들을 시도한다. 만약에 없다면 N-1번째 컬럼에 있는 Queen을 들어서 다음으로 가능한 칸으로 옮긴다. 다시 N번째 컬럼에 Queen을 둘 수 있는 곳을 찾는다. N-1번째 컬럼의 모든 경우를 시도했다면, N-2번째로 되돌아가 다음으로 가능한 위치로 Queen을 옮긴다.
구체적인 예를 들어보자. 정렬되어 있지 않은 숫자 리스트 중에 특정 숫자를 찾는 것은 n을 리스트 길이라고 했을 때, O(n) 시간 복잡도를 갖는다. 이 경우에는 백트래킹은 의미가 없다. 한 개씩 모두 살펴볼 수 밖에 없기 때문이다. 반면 N-Queen 문제의 경우는 다르다.
#include<iostream>
#include<vector>
#define MAX 5
using namespace std;
char Arr[MAX];
bool Check[MAX];
vector<char> V;
void Permutation(int n, int r)
{
if (n == r) {
for (int i = 0; i < V.size(); i++) {
cout << V[i] << " ";
}
cout << endl;
return;
}
for (int i = 0; i < MAX; i++){
if (Check[i] == true) continue;
Check[i] = true;
V.push_back(Arr[i]);
Permutation(n+1 , r);
V.pop_back();
Check[i] = false;
}
}
int main(void) {
Arr[0] = 'a';
Arr[1] = 'b';
Arr[2] = 'c';
Arr[3] = 'd';
Arr[4] = 'e';
Permutation(0,2);
}
#include<iostream>
#include<vector>
#define MAX 5
using namespace std;
char Arr[MAX];
bool Check[MAX];
vector<char> V;
void combination(int idx, int n, int r) {
if (n == r){
for (int i = 0; i < MAX; i++){
if (Check[i] == true){
cout << Arr[i] << " ";
}
}
cout << endl;
return;
}
for (int i = idx; i < MAX; i++) {
if (Check[i] == true) continue;
Check[i] = true;
combination(i,n+1,r);
Check[i] = false;
}
}
int main(void) {
Arr[0] = 'a';
Arr[1] = 'b';
Arr[2] = 'c';
Arr[3] = 'd';
Arr[4] = 'e';
combination(0,0,2);
}
위의 5가지 방법을 이용한 완전탐색 방법 모두를 익히는 것이 좋다.
모든 경우의 수를 탐색하는 방법은 문제를 접했을 때 가장 쉬운 방법이지만, 기초라고도 볼 수 있다. 그리고 문제에서 제한조건과 위의 몇 가지 SKILL을 추가하여 푼다면 문제 해결 시간을 크게 향상 시킬 수 있다. 참고로 완전탐색을 완벽하게 하기 위해서는 DFS, BFS 등등 코드를 두루두루 알고 있어야 한다.
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일합니다. DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.
N은 노드, E는 간선일 때
인접 리스트 : O(N+E) 인접 행렬 : O(N^2)
일반적으로 E(간선)의 크기가 N²에 비해 상대적으로 적기 때문에 인접 리스트 방식이 효율적이다.
3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용
DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제 단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다. 둘 중 편한 것을 사용하시면 됩니다.
2) 경로의 특징을 저장해둬야 하는 문제 예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
3) 최단거리 구해야 하는 문제 미로 찾기 등 최단 거리를 구해야 할 경우, BFS가 유리합니다. 왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.
이밖에도
검색 대상 그래프가 정말 크다면 DFS를 고려
검색 대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
4. DFS와 BFS을 사용한 c++코드
DFS 알고리즘에 경우 두 가지 방법으로 풀 수 있는데,
첫 번째로 스택을 이용하는 것 두 번째로 재귀함수를재귀 함수를 이용하는 것인데, 재귀 함수를 이용하는 것이 가장 보편적이고 짧은 코드를 작성할 수 있다. 재귀 함수란 함수 내부에서 함수가 자기 자신을 또다시 호출하는 함수를 의미합니다.
이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되기 때문에 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 합니다.
// DFS - Recursion
void dfs_recursion(int x, int y) {
// 함수에 들어왔으면 -> 방문으로 표시
visited[x][y] = true;
// 해당 단지의 집의 수를 증가시킴
groups[group_id]++;
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
dfs_recursion(nx, ny);
}
}
}
}
BFS 알고리즘은 큐(Queue)를 사용해서 문제를 해결하면 됩니다.
// BFS
void bfs(int x, int y){
queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.
// 처음 x,y를 방문 했기때문에
visited[x][y] = true;
groups[group_id]++;
while(!q.empty()){
// 큐의 현재 원소를 꺼내기
x = q.front().first;
y = q.front().second;
q.pop();
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;
// 해당 단지의 집의 수를 증가시킴
groups[group_id]++;
// 큐에 현재 nx,ny를 추가
q.push(make_pair(nx,ny));
}
}
}
}
}
힙(Heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)다. 최악의 경우가 생겨도 힙은 완전 이진 트리이므로 항상 O(logN)의 시간에 해결될 수 있도록 해준다.
힙을 이용한다면 최댓값 혹은 최솟값을 O(logN)에 찾을 수 있다. (일반 배열 사용시 O(N))
최대 힙(Max Heap) / 최소 힙(Min Heap)
최대 힙은 완전 이진트리의 root 부분에 최댓값이 항상 존재하게 되고 최소 힙은 완전 이진트리의 root 부분에 최솟값이 항상 존재하게 된다.
최대 힙의 특성: 임의의 subtree에서 root 가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최댓값을 유지한다.
최소 힙의 특성 : 임의의 subtree에서 root가 되는 노드를 잡으면 항상 subtree에서의 root 노드는 그 subtree에서 최솟값을 유지한다.
주의해야 할 점 : '힙의 자식 노드에서 작은 것이 왼쪽, 큰 것이 오른쪽' 이런 것은 존재하지 않는다. ⇒ 즉, 왼쪽 오른쪽에 무슨 노드가 오던간에 해당하는 subtree에서 루트노드보다 큰 (minheap에서는 작은) 값이면 된다.
실제 구현 시, 최소 힙은 최대 힙에서 음수 값으로만 구현해주면 되기 때문에 최대 힙 구현만 알고 있으면 됨.
최대 힙 삽입 과정(push)
Insert 할 값을 힙의 마지막 위치에 삽입한다.
부모 노드와 비교를 해서 Insert 할 값이 더 크다면 swap 해준다.
2번 과정을 계속 반복한다.
최대 힙 삭제 과정(pop)
pop 이기 때문에 root 부터 삭제하면 된다고 이해하면 될듯.
삭제할 값(root)를 빼낸다.
힙에서 마지막에 있는 노드를 root 로 올린다.
root로 올린 노드와 그 자식들의 노드를 비교해서 swap 해준다.
2~3번 과정을 반복한다.
이진 탐색 트리(Binary Search Tree) 와의 차이점
힙은 자식 노드가 부모 노드보다 크면 오른쪽으로 삽입, 작으면 왼쪽으로 삽입 과 같은 조건이 존재하지 않는다.
하지만 이진 탐색 트리에서의 노드 별 값 크기 순은 왼쪽 자식 < 부모 < 오른쪽 자식 순으로 된다.
보통 일반적으로 Heap 을 사용하기 위해서 C++ 에서는 Priority_queue 를 많이 사용한다. 이 때 코테에서 까먹지 않기 위해서는 일반적으로 선언해야 하는 메소드와 로직은 외우고 있어야 한다.
데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력 받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 방법으로, 궁극의 탐색 알고리즘이다.
해시 테이블의 성능은 공간을 팔아 얻어낸 것이라고 생각하면 된다.
보통 테이블의 엔트리는 <Key, value> 로 나타내며 이 때 value 는 key 로 인한 hash function 의 아웃 풋이다.
해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다.
허나 해시를 이용하면 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형 시간이 걸리기도 했던 것에 비해, 해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.
→ Hash Table 은 bucket 들과 그 bucket 을 이루고 있는 slot 들로 구성되어있다.
※ 해쉬 함수의 요구조건
계산하기 쉬워야 한다.
충돌의 횟수를 최소화 해야 한다.
편향되지 않아야 한다.
◇1. Direct Addressing Table
Direct Addressing Table 은 key-value쌍의 데이터를 배열에 저장할, key 값을 직접적으로 배열의 인덱스로 사용하는 방법이다.
예를 들면 키 값이 400인 데이터가 있다면, 이는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다.
똑같은 키 값이 존재하지 않는다고 가정하면, 삽입 시에는, 각 키마다 자신의 공간이 존재하므로 그 위치에다가 저장을 하면 되고, 삭제 시에는 해당 키의 위치에 NULL 값을 넣어주면 된다. 탐색 시에는 해당 키의 위치를 그냥 찾아가서 참조하면 된다.
찾고자 하는 데이터의 key 만 알고 있으면 즉시 위치를 찾는 것이 가능하므로 탐색 저장, 삭제, 갱신은 모두 선형시간 인 O(1) 로 매우 빠른 속도로 처리가 가능하다.
다만 key값이 최대 크기만큼 배열이 할당되기 때문에, 크기는 매우 큰데, 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 있다.
◇2. Hash Table
Hash Table 은 key-value 쌍에서 key 값을 테이블에 저장할 때, Direct Addressing Table과 달리 Key 값을 함수를 이용해 계산을 수행한 후,
그 결과 값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key 값을 계산하는 함수는 해쉬 함수(Hash Function) 이라고 부르며, 해쉬 함수는 입력으로 key를 받아, 0부터 배열의 크기 -1 사이의 값을 출력한다. 해쉬에 대한 첫 정의대로 임의의 숫자를 배열의 크기 만큼으로 변환시킨 것이다.
이 경우 k값이 h(k) 로 해쉬 되었다고 하며, h(k)는 k의 해쉬 값이라고 한다
2.1 충돌(Collusion)
하지만 해쉬 테이블은 '충돌'이 일어날 수 있다는 큰 문제점이 있다. 충돌이란, 다른 k값이 동일한 h(k)값을 가져 동일한 slot 에 저장되는 경우를 말한다.
예를 들자면 k1과 k12 을 해쉬하였더니 h(k1) = h(k12) 인 경우를 들 수 있다. Direcet Addressing Table 에서는 이를 방지하기 위해 모든 key 값이 다르다고 전제하였지만 해쉬 테이블에서는 key값이 달라도 해쉬의 결과가 같을 수 있기 때문에 이를 방지하기 위한 방법이 필요하다.
하지만 해쉬 함수를 아무리 잘 짜더라도 충돌을 '완전히' 방지한다는 것을 보장하기는 힘드므로, 충돌을 방지하기 위한 방법으로 충돌을 어느 정도 허용하되 이를 최소화 하는 방법도 사용하기도 한다.
Chaining 방법 - 충돌을 허용하되 최소화 하는 방법
충돌을 허용하지만 이를 최소화 하기 위한 방법 중 하나인 체이닝 방식이다. 체이닝이란 이름 그대로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 뜻하며, 해쉬 테이블에선 동일한 해쉬 값이 출력 되어 충돌이 일어나면, 그 위치에 있던 데이터에 key 값을 포인터로 뒤이어 연결한다. (마치 Linked List 처럼)
따라서 최초로 h(k) 위치에 저장된 데이터를 시작으로 그 이후의 h(k) 값이 출력되는 데이터는 모두
연결 리스트
의 형태를 취한다.
그렇기 때문에 최초의 위치를 탐색하는 해쉬 과정을 제외하고, 모든 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행한다.
Chaining 방법에서의 수행시간은 삽입 시에는 해쉬 값을 이용해 바로 slot 에 저장하면 되므로 상수 시간에 일어나고, 삭제는 연결리스트의 삭제와 동일하게 상수시간에, 탐색 시에는 견결 리스트를 따라가기 때문에 연결리스트의 길이 만큼 발생하지만, 최악의 경우, 즉 모든 데이터의 해쉬값이 일치하여 한 인덱스에 젖아됬을 경우엔 연결리스트의 탐색시간과 동일한 선형시간을 가지게 된다.
적재률
하지만 이 최악의 경우는 극단적인 예로써, 평균적인 경우엔 O(a+1)의 시간이 걸린다. a는 적재율을 뜻하며 적재율이란 현재 저장된 key값 갯수(K), 전체 테이블의 갯수(N)을 서로 나눈 값(K/N)이다. 즉 현재 저장된 데이터가 많으면 많아질수록 충돌 확률이 높아져 연결 리스트 탐색 확률도 증가하며, 적을수록 리스트 탐색 확률이 적어진다는 것이다.
Simple uniform hash
충돌을 최소화 하는 방법 중에 충돌이 적은 좋은 해쉬 함수를 만드는 방법도 있다. 좋은 해쉬 함수의 조건은 Simple uniform hash 함수를 만드는 것으로, 이 조건은 다음과 같다.
1. 계산된 해쉬 값들은 0부터 배열의 크기-1 사이의 범위를 '동일한 확률'로 골고루 나타날 것.
2. 각각의 해쉬 값들은 서로 연관성을 가지지 않고 독립적으로 생성될 것.
첫 번째 조건을 충족하면 충돌이 일어날 확률이 적어질 것이며, 두 번째 조건은 해쉬값들이 서로 연관이 있을 경우 연관성이 있으면 해당 해쉬 값이 등장하는 패턴이나 순서가 존재 할 수 있고, 이는 반복적인 충돌을 일으킬 확률이 있기 때문이다.
division method
해쉬 함수는 정말 다양하지만 대표적인 해쉬 함수로는 divison method가 있는데, modular 연산 방법을 이용하는 방법이다. 특정 key를 어떤 수로 나눈 나머지를 해쉬값으로 사용한다.
예를 들어 m=100이면 k mod m은 0부터 99까지의 범위를 가진다. 이 범위의 m은 해쉬 테이블의 성능을 크게 좌우하는데, m의 크기는 보통 키의 수의 3배가 적당하다고 한다. (적재율이 30%쯤까지 충돌이 거의 일어나지 않는다고 한다.)
그리고 m으로 2^p값을 사용하는 것엔 큰 주의를 요한다. 왜냐하면 m이 2^3이면, 2진수로 00001000이고, 4번째 이하의 숫자만 해쉬값에 영향을 끼치기 때문이다.
예를 들어 k1과 k2가 각각 10110100,10120100이면 둘 다 같은 해쉬값을 출력한다. 이를 방지하기 위해서 m은 보통 2^p에 근접한 소수를 선택한다고 한다.
◇ 정리
해시 알고리즘의 기초
인덱스를 사용하는 검색 알고리즘이다.
대용량의 데이터를 검색할 떄 주로 사용한다.
이진 검색 알고리즘과 병행해서 사용하면 빠른 검색 속도를 얻을 수 있다.
검색 성능 : O(1)
장점 : 데이터의 양에 관계 없이 빠른 성능을 기대할 수 있다.
해시 알고리즘에서 사용하는 몇 가지 용어
버킷 : 해시 주소 하나에 1개 이상의 데이터가 저장되는 전체 메모리 공간
슬롯 : 버킷에서 하나의 데이터가 저장되는 메모리 공간
충돌 : 서로 다른 데이터인데 같은 해시 주소를 갖게 되면 충돌이 발생한다.
오버플로 : 보통 충돌을 방지하기 위해 해시 주소 하나에 여러 슬록을 만들지만, 충돌이 계속해서 발생하여 데이터를 저장할 슬롯이 없어지는 상황
"오버플로" 해결방법
선형 조사 방법 : 해시 주소에 데잍어가 채워져 잇을 경우 옆자리를 확인하는 방법→ 데이터가 집중되는 현상 발생 (클러스터링)
링크드 리스트 사용 : 같은 해시 주소를 갖는 데이터를 배열이 아니라 링크드 리스트로 구성→ 클러스터링이 발생하면 링크드 리스트 내부에서 검색 작업이 발생해 순차 검색 해야 한다.
리해싱 : 다른 해시 함수를 사용해서 새로운 해시 주소를 생성하는 것→ 함수의 성능에 따라 알고리즘의 성능이 달라질 수 있다.
c++ 에서 해시 테이블을 구현하는 방법 중 대표적으로
unordered_map 이 있다.
코테보기 전에 이거 외우고 가자.
unordered_map 사용하기
map보다 더 빠른 탐색을 하기 위한 자료구조이다.
unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다.
map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)이다.
unordered_map을 사용하기 위해서는 #include< unordered_map > 을 선언해야 한다.
unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보인다.
하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있다.
함수
empty( )
맵이 비어있는지 확인하는 함수
if unordered_map is empty, then return 1 else 0
size( )
맵의 크기를 확인하는 함수
return size_type ( unsigned int )
operator [ ]
맵에서 key를 통해 value를 지정하는 operator
map_name[key] = value
find( key )
맵에서 key에 해당하는 원소를 찾는 함수
if key is contained, then iterator else map_name.end()
count( key )
맵에서 key에 해당하는 원소의 갯수를 반환하는 함수
if key is contained, return 1 else 0
insert( )
맵에 pair<key,value> 를 추가하는 함수
if key is contained, then not insert
erase( key )
맵에서 key에 해당하는 원소를 제거하는 함수
erase 하는 방법 : 특정 position의 pair 삭제, key를 통해 삭제, 범위 삭제
clear( )
맵을 초기화하는 함수
operator =
대입연산자 가능
※ 주의할 점
unordered_map 을 통해 for 문을 돌 때, vector 와 약간 다르다는 것을 알고 있어야 한다.
for (auto i = MapPlayer.begin(); i != MapPlayer.end(); ++i) {
if (i->second) {
iAnswer = i->first;
break;
}
}
위의 코드와 같은 방식으로 for 문을 돈다. 주의 할 점은 ++i 라는 것이다.
(또한 i→first , i→second 방식으로 원소를 뽑아낼 수 있다는 점을 알아둬야 할 듯.)
이제 어떻게 필터를 higher-level feature, 즉 의미있는 데이터를 뽑아내는 데에 사용할까에 대해 알아보자.
여기서 의미 있는 데이터란 edge, corner 와 같은 데이터를 의미한다.
◆2. templates matching
: 입력 이미지에서 템플릿 이미지의 위치를 찾는 방법이다.
template matching 은 template image 와 같은 사이즈의 window 를 가지고 source image의 모든 subimage 들과 비교하면서 유사도가 가장 높은 부분을 찾게 되는데, 크기가 같은 두 이미지 유사도를 구하는 방법 중 하나가 바로 NCC가 되는 것이다. (Normalized Cross Correlation)
NCC
: 각 픽셀들을 벡터라고 생각하자, (r,g,b) 이런식으로...
그리고 벡터를 정규화(normalize) 한다. 이 후 이 벡터들을 서로 내적했을 때 나올 수 있는 가장 큰 값은 얼마일까?
바로 1이다. 같은 두 벡터를 내적하는 경우이다. 반대로 가장 작은 값을 -1로 방향이 전혀 반대인 경우이다. 하지만 r,g,b 값은 음수가 없으므로 0이 최소이기도 하다.
다음은 NCC 를 구하는 식이다.
→ n : 픽셀의 개수
여튼 이런 식으로 template image 와 유사도가 가장 높은 subimage 를 찾아서 그 부분을 template 과 매칭시키면 물체 인식이 되는 것이다.
물론 이미지상에 물체가 존재하지 않을 경우를 생각해서 유사도가 threshold을 넘어가는 경우에만 인식하도록 하는 것이 좋다.
◆3. Edge detection
Edge 란?
1) Edge pixels
영상 내 특정한 픽셀 주변의 밝기 값이 급격하게 변하는 픽셀. 즉, pixel 의 불연속성을 통해 찾아낼 수 있다.
2) Edges
엣지 픽셀들의 연속된 집합. 어떤 것들이 이 Edge 를 발생시키나? 다음 그림을 보자.
적혀있는 대로 depth 의 차이 때문에 생기기도 하고,
3) 1차원에서 edge 감지하는 방법
: 1차 미분(변화량)을 구한다 ⇒
주변 값과의 차이
즉, 미분을 수행했을 때 크기가 0이 아닌 특정한 값을 가지는 부분을 활용해 edge를 검출할 수 있다.
4) 2차원에서 edge 감지하는 방법
: image gradient를 활용한다.
Gradient vector는 해당 픽셀의 변화량이 가장 급격한 방향(rapid change)을 가리킨다. Gradient vector와 Edge direction 은 수직관계에 있다.
여기서 알아두고 갈 것!
ⓐ Orientation ; 기울기 방향
ⓑ Magnitude ; edge 의 세기
5) Gradient의 방향을 구하면 Edge의 방향을 구할 수 있게 된다.
Derivatives with convolution
이 때 x축 기반의 경사와 y축 기반의 경사 각각으로 edge 를 감지할 수 있다.
Edge detection filter 의 종류
Prewitt
Sobel
Roberts
My = fspecial('sobel');
outim = imfilter(double(im), My);
imagesc(outim);
colormap gray;
◆4. Noise Image's Edge
이미지에 다음과 같이 노이즈가 껴있는 경우 Gradient 를 통한 edge 검출이 힘들 수 있다.
이러한 경우 어떻게 edge 를 찾아야 할까? 여러가지 방법이 있다.
ⓐ Smooth first
gaussian filter 를 통한 blur 처리로 노이즈를 잠재운 다음에 기울기를 찾을 수 있다.
ⓑ Derivative theorem of convolution
위의 방법에서 약간 순서만 바꾼 듯한 방식이다. step은 다음과 같다.
이게 왜 될까? 오른쪽의 공식이 성립하기 때문이다. 도함수를 따로 빼낸 다음에 계산을 해도 똑같다는 것을 알 수 있다.
두 방법 중에 Gaussian filter(low-pass filter의 일종) 의 미분을 구한 다음 기존의 이미지에 계산해주어 한번에 edge 를 찾는 것이 더 편해보인다. 이 때 Gaussian filter 의 미분 형태는 다음 두가지로 이루어져 있다.
어? 왜 갑자기 두 가지지? 이 질문에 대한 답은 이전 포스트에서 알 수 있다.
이전 포스트에서 Gaussian filter 의 분리가능성에 대해 잠깐 봤었다.
즉 이 성질에 의해 Gaussian 의 기울기 역시 각각 separate 된 놈의 기울기 곱으로 쪼개지기 때문에 위처럼 x축 방향, y축 방향 두 가지로 이루어져 있다고 봐도 무방하다.
여튼 이런식의 방법으로 noise 를 제거하면서 edge 를 찾을 수 있다. 하지만 이 때 사용되는 Gaussian filter 의 크기가 클 수록 blur 처리되어 edge 가 검출이 되니 이점만 주의하자. 다만 어느게 정답인 거인지는 그때그때 다르다.
Laplacian of Gaussian
도함수의 도함수를 통해 noise 를 감안한 edge 도출 역시 가능하다. 이 때는 다만 급격한 변화가 아닌 0을 통과하는, 즉 부호가 바뀌는 부분이 edge 이다.
또한 라플라시안 역시 x, y 축 기준으로 쪼갤 수 있다. (separate 가능!)
◆5. Edge Dectector
Thresholding
어떻게 pixel 을 솎아내어 최적화 할까? 에 대한 하이퍼파라미터 설정이 필요하다. 이 역시 비전 공학의 특성에 맞게끔 그때그때 융통성 있게 처리해야 한다고 한다.
위의 그림을 예시로 들었을 때, higher threshold 에 의해 뽑아내진 edge 가 더 인식하기 좋다는 것을 알 수 있다.
ⓐ Canny edge detector
Gaussian 으로 noise를 다룬 후 edge 를 뽑아내는 방법이다. 특이한 점은 Non-maximum suppression 으로 여러개의 edge 가 도출 된 경우 가장 선명한 edge 를 뽑아내는 방식을 사용한다는 점이다.
이 NMS 는 edge 뿐 아니라 detection 할 때에도 사용하니 알아두자.
다음 그림들이 Canny edge detector 를 사용한 예시이다. canny는 threshold 를 주어 edge 를 적절히 솎아낼 수 있으며 가우시안 필터를 통해 노이즈 처리 후 edge 를 검출한다는 거 알아두자.
Non-maximum suppression
위에서 말했듯이 기울기가 여러 개 있을 때 가장 큰 값을 선택한다는 방식을 이야기한다.
여튼 이 NMS 와 Thresholding 방식으로 edge 를 찾게 되었을 때 분명히 edge 인데 threshold 보다 작아 살아지는 문제가 생길 수 있다. 보통 곡선에서 이 문제가 많이 일어난다.
이 문제를 해결하기 위해 Hysteresis thresholding 방식을 사용한다.
오류를 최소화하기 위해 자신의 값 뿐만 아니라 주변의(공간적 또는 시간적으로) 값을 같이 참조하는 것이 효과적이다.
Hysteresis thresholding은 주변의 분류 결과에 따라서 자신의 분류 결과가 달라질 수 있는 thresholding 기법으로서 Canny edge detector에 사용된 이진화 기법이 가장 대표적인 예이다.
Hysteresis thresholding 방식의 과정은 다음과 같다.
high threshold와 low threshold의 두 개의 threshold 값이 존재하며 high threshold 이상의 edginess 를 갖는 픽셀들은 무조건 edge 픽셀로 분류한다.
low와 high 사이에 있으면서 이미 edge로 분류된 픽셀들과 연결되어(인접해) 있으면 edge 픽셀로 분류한다.
나머지 픽셀들(low threshold 이하이거나 high threshold 이하이면서 edge 픽셀과 연결되어 있지 않은 경우)은 모두 non edge 픽셀로 분류한다.
작은 센서를 만들 때, 저녁이라는 시간 때문에 생기는 노이즈와 같은 문제가 생길 수 있다. 즉 이러한 경우 적당한 필터링을 통해 노이즈를 제거해주어야 한다. 이럴 때 쓰이는 필터란 무엇일까에 대해 알아보자.
1. Image?
Intensity values (집약정도) 를 사용해 매트릭스 혹은 격자의 형태 로 표현한다.
즉, 이미지는 정수값의 행렬로 표현된다~ 정도만 알아두자.
Images as functions : r,g,b 총 세 개의 함수가 내장되어있는 거라고 볼 수 있다.
2. Image 특성
이미지는 제한된 수만큼 픽셀을 보유한다.
픽셀 값→ grayscale은 0~255
→ 컬러의 RGB 같은 경우, 각 채널 당 0~255 까지 각 1바이트로 총 3바이트 표현 가능하다.
3. Image 변환
수학적인 함수를 이용해서 operator 를 적용하면, 이미지 변환을 얻을 수 있다.
대표적인 operator 로 convolution 이 있으며 거의 노이즈 제거에 이용 된다.
4. Why Noise?
이미지 획득하는 과정에서 생길 수도 있고, 카메라 자체의 문제로 생길 수도 있고, 인화 단계의 문제에서 생길 수도 있다.
Noise type
Salt and pepper noise (백색 잡음) : pixel 단위로 어긋난 형태의 노이즈
Impulse noise : pixel 단위로 어긋난 형태의 노이즈
Gaussian noise : 랜덤 값이 연속적으로 증감한 형태의 노이즈
정규분포를 가지는 잡음을 이야기한다. 쉽게 말해 일반적인 잡음이며 어느 정도 랜덤하게 자연계에서 쉽게 볼 수 있는 분포를 말한다.이 노이즈를 큰 표준편차의 Gaussian filtering을 해서 해결할 수는 있지만 이미지도 같이 blur 처리 되기도 한다는 점 알아두자. (뒤에서 도움 됨)시그마에 따라 노이즈의 정도가 달라지게 된다.
5. 노이즈 제거
가장 그럴싸한 방법은 제일 근처의 값들이 비슷한 pixel 값을 가질 가능성이 크므로, 주변 값을 보는 방법이다.
즉, 현재 픽셀을 주변 픽셀들과 평균을 내서 대치를 하게 되면 조금 더 원래 값에 가까이 가지 않을까? 라는 접근 방법에서 시작된 방법이다. (Mean Filtering)
→ Mean filtering 을 적용하면 노이즈들이 제거되고, 디테일 부분을 블러링으로 사라진다.
6. Filtering Type
: 일단 필터링이란 새로운 이미지를 만드는 것을 이야기 한다.
영상에서의 filtering이란 원하는 성분을 추출하는 과정이라 말할 수 있다.
영상 처리에서 filtering은 크게 spatial filtering과 frequency domain filtering이 있다.
spatial filtering은 영상을 그대로 이용하여 원하는 성분을 추출하는 것이며, frequency domain filtering은 영상을 주파수 공간으로 변환하고 주파수 공간에서 처리하는 것이다.
filter 의 종류로는 다음과 같은 것들이 있다.
Correlation filter
Gaussian filter
Averaging filter
Linear filter
7. Linear filtering
Correlation, Convolution은 모두 Linear filtering 방법의 종류다. 즉, 영상과 kernel을 어떠한 방식으로 filtering할 것인가 하는 방법들이다. 이 section에서 예시로 사용될 kernel은 3x3으로 아래 그림과 같다.
Correlation
먼저 영상 I의 임의의 점 I(x,y)에 대해 kernel과 correlation 연산을 통해 결과를 생성하는 것을 수식으로 표현하면,
이러한 과정을 그림으로 쉽게 표현해보면,여기서 "가장 최 상단의 pixel들은 중심점으로 두지 않나?" 라는 의문점이 생길 수 있다. 가장 최 상단(최 하단, 좌측, 우측)에 해당하는 pixel을 filtering하기 위해서는 kernel의 상단에 matching되는 값들이 필요하다.따라서, 검은색 테두리나, 영상의 크기가 작아지는 것을 방지하기 위해 흔히 padding이라는 것을 사용한다. padding은 원 영상 테두리에 특정 값을 채워 넣음으로써 filtering된 영상의 크기를 원 영상의 크기와 동일하게 유지할 수 도 있으며 검은색 테두리를 방지할 수 도 있다. (흔히 사용되는 값은 0으로, zero-padding으로 불린다.)
허나 다음과 같이 MATLAB의 옵션만 바꿔주어도 끝부분을 처리해줄 수 있다.
만약, 최상단(혹은 최하단, 가장 좌측, 우측에 존재하는 pixel들)의 pixel들을 filtering에 포함하지 않는다면, filtering된 결과 영상의 크기는 원래의 영상보다 작아지거나, 주변이 0으로 채워져 원 영상의 크기를 유지한다고 해도 검은색 테두리가 생기는 결과를 받을 수 있다.
즉, 영상 I의 점 x,y와 kernel의 중심점(Anchor)을 matching하고 주변의 pixel들을 각각 곱해 중심점에 모두 합 산 하는 연산이다. 해당 점에 대해 연산이 끝났다면 한 칸 이동 (대부분 오른쪽으로 한칸 이동, 가장 우측에 도달했다 면 다시 한 칸 아래 좌측 처음으로 옮겨 영상의 마지막 우측 하단 pixel에 도달할 때 까지 반복한다.)하여 이 filtering 을 반복한다
Convolution
사실, convolution과 correlation 연산은 영상 처리에서 혼용되어 부르기도 한다. 하지만, 그 쓰임새는 다르다. correlation 연산이 kernel과 matching되는 pixel들의 곱셈, 그리고 곱셈 결과들의 총 합이다.
Shift invariance 때문에 → 쉬프트가 된다 해도, convolution 에는 영향이 없다.
linearity 때문에 → 인풋이 변하게 될 때 우리가 예상할 수 있는 방향으로 간다.
Convolution이 중요한 이유 : 만약 correlation 연산으로 convolution 연산을 한 것과 동일한 효과를 보려면 convolution kernel로 correlation을 진행하면 된다. correlation은 유사성을 check하기에 적합하며 convolution은 smoothing과 같은 용도로 사용한다고 한다.
이러한 filtering 이라는 게 왜 필요한가?
새로운 유용한 정보를 얻기 위해서 : edge나 contours와 같은 정보를 뽑아내기 위해 사용하기도 한다.
이미지 enhance 를 위해 : 노이즈 제거를 위한 blurring, enhance(sharp) image를 위해 사용된다.
convolutional nerual networks 의 key operator를 위해 사용하기도 한다.
8. Mean filtering
Mean filtering은 주변의 평균으로 pixel 값을 대체하는 방식의 필터링이다. Gaussian 과는 다르게 모든 pixel 들에 같은 가중치를 주어 평균치를 내는 방법이
9. Gaussian filtering
주변의 픽셀들이 멀리있는 픽셀보다 관련성이 높다, 가까운 픽셀에 더 많은 가중치!
보통 이 Gaussian filter 를 이미지의 edge 와 같은 high-frequency component 를 줄이기 위해 사용하여 low-pass filter 라고도 부른다.
또한 보통 가우시안 필터링을 할 때 다음 그림과 같이 행렬을 쪼개 계산을 해준다.
이런식으로 분리하면 2차원의 행렬을 1차원 두개로 나누게 되어 시간복잡도를 매우 줄일 수 있다.
즉, 결합법칙과 같은 행렬 연산 법칙에 의해 한 차원이 줄어들게 되는 효과를 얻을 수 있다는 것을 알 수 있다.
10. Median Filter vs Mean Filter
두 개의 비슷한 필터를 잠깐 비교해보자.
그림을 봤을 때 Median 의 경우 하나의 pixel 값만 보정되었지만 Mean 은 근접한 놈의 평균으로 나타내기 때문에 전체적으로 값이 다 바뀌게 된다.
Gaussian vs median filtering
그러면 이 두 개를 비교해보자.
확실히 Salt & pepper noise 는 Median 이 더 성능 좋게 노이즈를 제거해준다. 허나 filter 사이즈가 크면 클 수록 이미지의 해상도 및 데이터가 이상해질 수 있따.
11. Sharpening
Sharpening 이란 edge 를 강조해주는 듯한 기법이다.
어떤 필터를 써야 sharpening 효과를 가질 수 있을까?
→ 블러링 이미지의 경우에는 오리지널에서 디테일이 없다는 특징을 이용한다.
수식은 다음과 같다.
12. Sharpening revisited
어떻게 Sharpening 을 계산하는 지를 알아두자. 또한 Gaussian 과 비슷한 Laplacian 에 대해서도 알아두자. 다음 그림처럼 계산 후 계수 식을 묶어 처리하는 방법이다.
