태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
2014.04.11 15:15



 android, flood fill algorithm performance tests.

 

 android, flood fill algorithm performance tests.



[android] flood fill algorithm performance tests.


위와 같은 공룡의 엉덩이, 발, 그리고 꼬리에 이르는 부분을 FloodFill algorithm 을 적용하여 색칠해보았다.

avg 값은 5회의 결과를 평균 낸 값이다.



1. Very Intuitive and Simple Flood Fill Algorithm


Recursive method call 을 이용하여, 한 점을 기준으로 동,서,남,북 pixel 에 대해 recursive call 을 호출하는 방식이다.


private void floodFill3(Bitmap bitmap, Point fillStartPoint, int targetColor, int replacementColor){

Queue<MyPoint> queue = new LinkedList<MyPoint>();

queue.add( new MyPoint( fillStartPoint ) );


while (queue.size() > 0) {

MyPoint node = queue.poll();

    if ( bitmap.getPixel( node.x, node.y ) != targetColor ) continue;

    bitmap.setPixel( node.x, node.y, replacementColor );

    

    if ( !node.isFromWest() && node.x-1 > 0 )

     queue.add( new MyPoint( node.x-1, node.y, MyPoint.FROM_EAST ) );

    if ( !node.isFromEast() && node.x+1 < mBitmapWidth )

     queue.add( new MyPoint( node.x+1, node.y, MyPoint.FROM_WEST ) );

    if ( !node.isFromSouth() && node.y+1 < mBitmapHeight )

     queue.add( new MyPoint( node.x, node.y+1, MyPoint.FROM_NORTH ) );

    if ( !node.isFromNorth() && node.y-1 > 0 )

     queue.add( new MyPoint( node.x, node.y-1, MyPoint.FROM_SOUTH ) );

}

}


avg = 2015.4 ms.


onDraw 에서 floodFill logic 을 수행하기 떄문에,

2초나 UI thread 를 막는 결과를 초래했다. 

이 녀석을 사용할 수 없다. 다른 방법을 찾아봐야 한다.








2. Better but little bit Complex Flood Fill Algorithm.


Recursive Call 은 stack overflow 를 발생시킬 소지가 다분하며, 기본적인 algorithm 은 효율성이 떨어진다.

Wiki 를 참조하여 더 나은 방법을 찾았으니,

한점을 기점으로 좌, 우의 pixel 포인트를 정하고,

그 점의 위, 아래 pixel 에 대해 이 logic 을 recursive 하게 돌리는 것이다.


단, 진짜 recursive call 이 아닌, Queue 와 같은 collection 을 이용하 loop 를 recursive 하게 돌리는 것이다.


private void floodFill(Bitmap bitmap, Point fillStartPoint, int targetColor, int replacementColor){

Queue<Point> queue = new LinkedList<Point>();

queue.add(fillStartPoint);


while (queue.size() > 0) {

    Point node = queue.poll();

    if ( bitmap.getPixel( node.x, node.y ) != targetColor ) continue;


    Point westNode = node;

    Point eastNode = new Point( node.x + 1, node.y );

    

    while ( (westNode.x > 0) && (bitmap.getPixel( westNode.x, westNode.y ) == targetColor) ){

     expandToUpDownNode( queue, bitmap, westNode, targetColor, replacementColor );

        westNode.x--;

    }

    

    while ( (eastNode.x < mBitmapWidth ) && (bitmap.getPixel(eastNode.x, eastNode.y) == targetColor) ) {

     expandToUpDownNode( queue, bitmap, eastNode, targetColor, replacementColor );

        eastNode.x++;

    }

}

}


private void expandToUpDownNode( Queue<Point> pointQueue, Bitmap bitmap, Point node, int targetColor, int replacementColor ){

bitmap.setPixel( node.x, node.y, replacementColor );

    if ( (node.y > 0) && ( bitmap.getPixel( node.x, node.y - 1) == targetColor ) )

     pointQueue.add( new Point( node.x, node.y - 1) );

    if ( (node.y < mBitmapHeight) && ( bitmap.getPixel( node.x, node.y + 1 ) == targetColor ) )

     pointQueue.add( new Point( node.x, node.y + 1 ) );

}


avg = 1288 ms.


확실히 기본 recursive algorithm 에 비해서는 약 2배의 성능향상이 있었지만,

아직도 onDraw 에서 그려 UI Thread 를 약 1초 이상 hold 시키기 때문에 사용성 문제로 

performance optimization 이 더 수행되어야 한다.







3. 안드로이드 최적화 가이드에서 제시하는 방법들 적용.


3-1. function remove.

recursive 는 아니더라도, function call 자체도 필요 이상으로 불리게 되면 ( 지나친 refactoring 의 폐해 )

성능저하를 가져올 수 있다고 한다.

그래서 위 코드의 expandToUpDownNode 를 제거하고, 그 코드를 floodFill method 안에 그대로 넣어주었다.


avg = 1215ms.


표본수가 부족하기 때문에 정확한 성능향상이 있었다고 이야기하기는 어렵지만,

그냥 눈에 보이기에는 미약하게나마 조~금 좋아보인다..



3-2. use local variable.


안드로이드 최적화 가이드에서는 2회 이상 사용하는 global variable 들에 대해서

local variable 로 assign 하여 사용하는 것을 추천하고 있다.

같은 범주에 있더라도, local 이 훨씬 접속하는데 성능이 좋다는 것이리라..

그래서 위에서 bitmap 의 width 나 height 같은 부분을 local 로 바꾸어 적용해보았다.


avg = 1208ms.


이 역시 표본수 부족으로 확신을 할 수는 없지만, 눈에 보이기에는 미약하게나마 조금 성능향상이 있는 것 같다.



3-3. MyPoint 적용.


기본 Point 에는 x, y 값 뿐만 아니라 이것저것 다른 function 들도 들어있다.

"그럴리는 없겠지만" 하는 생각과 함께, 혹시나 몰라 MyPoint 라는 녀석을 만들어 다른 기능은 싹 빼고,

x, y 만 정의해서 사용하는 방법을 적용해보았다.


private static class MyPoint2{

public int x;

public int y;

public MyPoint2( int x, int y ){

this.x = x;

this.y = y;

}

}


avg = 1179.2 ms.


역시나 표본수 부족으로 신뢰가 가는 결과는 아니지만,

그래도 역시나 눈에 보이는대로는 약간의 성능 향상이 있었다.







4. 성능이슈는 역시나 JNI.


JNI 는 Java Native Interface 의 약자로, C, C++ 과 같은 Native 언어로 복잡도가 높은 코드를 수행하고,
그 결과를 다시 Java 단으로 전달하는 것을 이야기한다.

Java 는, 특히 Android 의 경우는 VM ( Dalvik ) 이 Native code 에 비해 성능이 느린 것은 익히 알려진 사실이다.
물론 JNI 를 통하면 NDK 도 있어야 하고, 복잡도도 올라가고, debugging 등도 어렵고, 이해해야 할 것도 훨씬 많긴 하지만, 그래도 성능향상의 결과는 확실했다.


avg = 34 ms.


표본수 부족이라는 핑계는 전혀 댈 수 없을정도로 엄청난 성능향상이 있었다.

가능한 복잡도 높은 operation 은 이제 무조건 JNI로!!!


더보기





저작자 표시 비영리 변경 금지
신고

댓글을 달아 주세요

  1. 안드로이 2014.05.12 10:38 신고  댓글주소  수정/삭제  댓글쓰기

    http://stackoverflow.com/questions/8070401/android-flood-fill-algorithm
    여기에 보면 QueueLinearFloodFiller 클래스가 있는데.. 빨라요..

  2. 2014.05.22 12:07  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

    • 돼지왕왕돼지 2014.05.23 11:16 신고  댓글주소  수정/삭제

      음. 제 앱을 사용해보시면 아시겠지만 dpi 가 올라갈수록 저도 안티알리아싱 효과가 조금씩 나타나고 있습니다. 가장 빠른 해결책은 해상도에 딱 맞는 이미지를 로드하여 scaling 이 나타나지 않도록 하는 방법이라고 생각됩니다.

  3. 비기너 2014.05.29 15:48 신고  댓글주소  수정/삭제  댓글쓰기

    색채우기를 하면 테두리 부분이 하얗게 덜칠해지는데 혹시 왜그런지 아시나요?
    그리고 jni 테스트를 한번 해보고 싶은데 ㅠㅠ 혹시 코드를 알려주실 수 있나요? 없으시면 할 수 없구요!
    색칠하기에 관한글이 잘 없네요 ㅠㅠ


Posted by 돼지왕왕돼지