Wednesday, October 11, 2017

Markov โมเดล แบบบ้านๆ ตอนที่ 3 - Hidden Markov Models

ถ้าจะสรุปจากบทความก่อนหน้านี้ เราอาจพอบอกได้ว่า Markov model คือโมเดลรูปแบบหนึ่ง ที่ใช้พยากรณ์เหตุการณ์ใดๆ จากข้อมูลความน่าจะเป็นของเหตุการณ์ในอดีต โดยมีสมมติฐานว่า ความน่าจะเป็นของเหตุการณ์ใด จะขึ้นอยู่กับเหตุการณ์ก่อนหน้านั้นอย่างจำกัดเหตุการณ์ ซึ่งโดยทั่วไปจะสนใจเฉพาะเหตุการณ์ก่อนหน้าเพียงแค่เหตุการณ์เดียว ซึ่งเราเรียกว่า 1st order Markov assumption หรือสั้นๆ แค่ Markov assumption

แล้วอะไรคือ Hidden Markov Model (HMM) ล่ะ

ตามชื่อซึ่งมีคำว่า Hidden ก็หมายถึงว่า เราไม่ทราบเหตุการณ์ก่อนหน้าอย่างชัดเจน หรือการพยากรณ์ต้องใช้ปัจจัยอื่นมาเทียบเคียงด้วย

ก่อนหน้านี้ หากเราจะพยากรณ์สภาพอากาศที่ยังไม่เกิดขึ้น เราจะต้องทราบถึงสภาพอากาศในอดีตก่อน
แต่ถ้าเราไม่รู้ข้อมูลในอดีต หรือข้อมูลดังกล่าวถูกปกปิดไว้ (Hidden) จะคาดการณ์ได้อย่างไร

HMM เสนอว่า แม้ว่าเราจะไม่รู้ว่าเหตุการณ์ในอดีตเป็นอย่างไร (แต่ต้องรู้เหตุการณ์เริ่มต้น) ถ้าเราพอทราบเหตุการณ์ที่เกี่ยวเนื่องกัน ก็อาจเทียบเคียงเพื่อใช้พยากรณ์ได้

ตัวอย่างเช่น
สมมติว่าเราถูกขังไว้ในห้อง โดยไม่รู้สภาพอากาศจริง แต่ทราบว่ามีความสัมพันธ์ระหว่างสภาพอากาศกับการใช้ร่มของคนที่มาเยี่ยมเราในทุกๆวัน เช่น

ถ้าสภาพอากาศมีแดด ฝน และ หมอก โอกาสที่คนมาเยี่ยมจะพกร่มจะเป็น 0.1, 0.8 และ 0.3 ตามลำดับ และโอกาสที่คนมาเยี่ยมจะพกร่ม (โดยไม่สนใจสภาพอากาศเลย) คือ 0.5

สมมติว่าวันที่เราถูกขังไว้ในห้องเป็นวันที่มีแดด วันต่อมาคนมาเยี่ยมพกร่มมาด้วย โอกาสที่ฝนจะตกวันนี้เป็นเท่าใด

สิ่งที่เราต้องการจะหาคือ P(w2=rainny | w1=sunny, u2 = true)
เมื่อ w1 และ w2 คือเหตุการณ์สภาพอากาศเมื่อวาน (วันแรก) และวันนี้ (วันที่สอง) ตามลำดับ
และ u2 คือเหตุการณ์ที่คนมาเยี่ยมจะพกร่มในวันนี้ (วันที่สอง)

สิ่งที่เรารู้คือ ความน่าจะเป็นของสภาพอากาศที่ต่อเนื่องกัน P(w2 | w1) และ ความน่าจะเป็นที่ผู้มาเยี่ยมจะพกร่มในสภาพอากาศต่างๆ P(u | w) และความน่าจะเป็นที่ผู้มาเยี่ยมจะพกร่มโดยไม่ขึ้นกับสภาพอากาศ P(u)

ดังนั้นจำเป็นต้องจัดรูปแบบความสัมพันธ์ใหม่ ให้อยู่ในรูปของสามค่านี้

ก่อนอื่น มาทบทวนความน่าจะเป็นแบบมีเงื่อนไขกันเล็กน้อย
P(A|B) = P(A,B) / P(B)
หรือ
P(A,B) = P(A|B) P(B) = P(B|A) P(A)

ดังนั้น จากที่เราต้องการหา P(w2=rainny | w1=sunny, u2 = true)  ผมขอเขียนง่ายๆว่า P(w2 | w1, u2) นะครับ

P(w2 | w1, u2) = P(w2, w1, u2) / P(w1, u2)
= P(w2,w1 | u2) P(u2) / [ P(w1 | u2) P(u2) ]
= P(w2,w1 | u2) / P(w1 | u2)

แต่เนื่องจากเหตุการณ์ w1 กับ u2 ไม่ขึ้นต่อกัน (คนละวัน) P(w1 | u2) = P(w1) ตอนนี้สิ่งที่เราต้องการหาเลยเหลือเป็น
= P(w2, w1  | u2) / P(w1)

แต่เราไม่สามารถหาค่านี้ได้ เพราะสิ่งที่เรารู้มันกลับกันคือ P(u|w) ดังนั้น
เราจะใช้ทฤษฎีของ Bayes ที่เอาไว้เปลี่ยนลำดับของความน่าจะเป็นแบบมีเงื่อนไข
P(A|B) = P(B|A) P(A) / P(B)

= P(w2, w1  | u2) / P(w1)
= P(u2 | w2,w1) P(w2, w1) / P(u2) / P(w1)

จาก Markov assumption เราสนใจเฉพาะข้อมูลสภาพอากาศวันล่าสุดเท่านั้น เลยจะได้ว่า P(u2 | w2,w1) มีค่าเป็น P(u2, w2) ความสัมพันธ์ใหม่ก็เลยเหลือ
= P(u2 | w2) P(w2, w1) / [P(u2) P(w1)]

จัดรูปต่ออีกหน่อย เพราะเหลือค่าที่ไม่รู้คือ P(w2, w1) และ P(w1) ซึ่งเรารู้ว่าค่า P(w2, w1)/P(w1) มีค่าเท่ากับ P(w2 | w1)

สุดท้ายจึงได้
= P(u2 | w2) P(w2 | w1) / P(u2)

ซึ่งเมื่อกลับไปเขียนเต็มๆ จะได้ว่า
= P(u2 = true | w2 = rainy) P(w2 = rainy | w1 = sunny) / P(u2 = true)
และแทนค่าจะได้เป็น
= 0.8 x 0.05 / 0.5
= 0.08

นั่นคือ ความน่าจะเป็นที่ฝนจะตกวันนี้ เมื่อวันนี้คนมาเยี่ยมพกร่ม และเมื่อวานเป็นวันมีแดด คือ 0.08

มันก็จะงงๆตรงความน่าจะเป็นหน่อยนะครับ

Tuesday, July 18, 2017

Markov โมเดล แบบบ้านๆ ตอนที่ 2 - 1st order Markov assumption

เราลองมาดูตัวอย่างจาก Reference เดิมเพิ่มเติมกันครับ

ตัวอย่างที่แล้ว เราคาดการณ์เหตุการณ์ที่สามและสอง จากเหตุการณ์ที่ 1

จะเป็นอย่างไร ถ้าเราจะคาดการณ์เหตุการณ์ใดๆ จากเหตุการณ์ตั้งต้น เช่น เหตุการณ์ที่สามจากเหตุการณ์ที่ 1 เลย

สมมติว่าเรายังใช้ความน่าจะเป็นจาก finite state automaton รูปนี้
ตัวอย่างที่ 2 ถ้าวันนี้มีหมอก จงหาความน่าจะเป็นที่ฝนจะตกในวันมะรืน

ก่อนอื่นลองพิจารณาดูก่อนว่า จะมีกี่หนทางที่จะเกิดเหตุการณ์นี้ได้ จากสภาพอากาศ
วันนี้ -> พรุ่งนี้ -> มะรืน
ก็จะเป็นไปได้สามรูปแบบคือ
1. หมอก -> หมอก -> ฝน
2. หมอก -> ฝน -> ฝน
3. หมอก -> แดด -> ฝน

นั่นคือ ความน่าจะเป็นที่โจทย์ถาม ก็คือผลรวมของความน่าจะเป็นในแต่ละช่องทาง

P(W_3 = rainy | W1 = foggy)
 = P(W3 = rainy, W2= foggy | W1 = foggy) + P(W3 = rainy, W2= rainy | W1 = foggy) + P(W3 = rainy, W2= sunny | W1 = foggy)

คล้ายๆตัวอย่างที่แล้ว โดยใช้การประมาณ Markov เรารู้ว่า
 P(W3 = rainy, W2= foggy | W1 = foggy)
=  P(W3 = rainy | W2= foggy , W1 = foggy) * P(W2 = foggy | W1= foggy)
=  P(W3 = rainy | W2= foggy) * P(W2 = foggy | W1= foggy)

ดังนั้น ย้อนกลับไปสมการก่อนหน้านี้ จึงได้ว่า
P(W3 = rainy | W1 = foggy)
=  P(W3 = rainy | W2= foggy) * P(W2 = foggy | W1= foggy) + P(W3 = rainy | W2= rainy) * P(W2 = rainy | W1= foggy) + P(W3 = rainy | W2= sunny) * P(W2 = sunny | W1= foggy)
= (0.3*0.5) + (0.6*0.3) + (0.05*0.2)
= 0.15 + 0.18 + 0.01
= 0.34

Markov โมเดล แบบบ้านๆ ตอนที่ 1 - 1st order Markov assumption

วันนี้มาทางวิชาการกันหน่อย ผมจะขอสรุปเนื้อหาของ Markov models ตามเอกสารอ้างอิงนี้
Eric Fosler-Lussier, Markov Models and Hidden Markov Models: A Brief Tutorial, December 1998

ซึ่งเขียนอธิบายไว้ดีมาก รวมกับความเข้าใจของผมเอง อาจจะมีคำบัญญัติภาษาไทยแบบที่ผมเขียนเองบ้าง ขอให้ดูความหมายภาษาอังกฤษกำกับเพื่อเทียบกับตำราเล่มอื่นนะครับ

ก่อนอื่นคือเราอาจจะมีคำถามว่า Markov model มีไว้ทำอะไร ถ้าเอาแบบง่ายๆสั้นๆ ก็คือ เป็นโมเดลทางคณิตศาสตร์แบบหนึ่ง ที่ไว้คาดการณ์หรือพยากรณ์เหตุการณ์ในอนาคต จากข้อมูลในอดีต


ผมจะลองยกตัวอย่างจากเอกสารอ้างอิงนะครับ

สมมติว่าเราอยากพยากรณ์อากาศของวันพรุ่งนี้ ถ้าเราไม่มีข้อมูลภาพถ่ายดาวเทียมหรือข้อมูลทางภูมิศาสตร์อื่นๆเลย เราอาจจะสามารถทำได้โดยการใช้ข้อมูลของวันที่ผ่านๆมา

ถ้าสภาพอากาศมีแค่สามแบบ คือ มีแดด (sunny) มีฝน (rainy) และ มีหมอก (foggy) ตลอดวันในแต่ละวัน

เมื่อเราลองเก็บสถิติสภาพอากาศในแต่ละวัน แล้วคำนวณหาค่าความน่าจะเป็นของสภาพอากาศวันพรุ่งนี้ เมื่อทราบสภาพอากาศของวันนี้ เราอาจจะได้ตารางความน่าจะเป็นแบบมีเงื่อนไข (conditional probability) ดังข้างล่าง


ความหมายของตารางจะเป็นดังตัวอย่างต่อไปนี้ เช่น
-ถ้าวันนี้มีแดด โอกาสที่พรุ่งนี้จะฝนตกคือ 0.05
ซึ่งเราสามารถเขียนเป็นสมการได้ดังรูป
 P(W2 = rainy | W1=sunny)
 เมื่อ W2 และ W1 แทนสถานะ (สภาพอากาศ) ณ วันพรุ่งนี้และวันนี้ตามลำดับ

ให้สังเกตว่าผลรวมของความน่าจะเป็นในแต่ละแถวจะเท่ากับ 1

ซึ่งก็อาจจะเอามาเขียนเป็น finite state automaton หรือ state transition diagram ได้ตามรูปนี้


อย่างไรก็ตาม ข้อมูลนี้ก็ใช้พยากรณ์ได้วันต่อวัน ถ้าต้องการพยากรณ์ข้อมูลถัดไปอีกสองวัน (วันมะรืน) เมื่อทราบข้อมูลวันนี้ ก็จะทำไม่ได้โดยตรง นั่นคือ ต้องเก็บข้อมูลเพิ่มและคำนวณหาความน่าจะเป็นใหม่อีก ซึ่งจำนวนข้อมูลที่ต้องเก็บจะเท่ากับ จำนวนสถานะยกกำลังด้วยจำนวนวัน ข้อมูล ซึ่งในที่นี้เรามีสามสถานะ และสนใจสามวัน ก็จะต้องเก็บอย่างต่ำ 3^3 ข้อมูลเพื่อมาคำนวณหาความน่าจะเป็น

เพื่อที่จะทำให้งานง่ายลง เราสามารถใช้การประมาณมาทดแทน โดยกำหนดว่าถ้าต้องการพยากรณ์ข้อมูลวันนี้ ให้ใช้ข้อมูลของวันก่อนหน้านี้เท่านั้น นั่นคือ
P(Wn | Wn-1, Wn-2, ..., W1) มีค่าประมาณ P(Wn | Wn-1)

การประมาณนี้มีชื่อเรียกว่า การประมาณ Markov ในลำดับชั้นแรก (First-order Markov assumption) หรือเรียกสั้นๆว่า การประมาณ Markov (Markov assumption) ซึ่งจะทำให้เราลดการเก็บข้อมูลจาก สถานะ^n เหลือแค่ สถานะ^2 เพราะสนใจข้อมูลแค่สองเวลา

กลับมาที่ตัวอย่างเรื่องสภาพอากาศ ถ้าเราใช้การประมาณ Markov แล้วเราจะสามารถตอบคำถาม "สภาพอากาศของวันมะรืนจะเป็นอย่างไร ถ้าทราบสภาพอากาศของวันนี้"

การตอบคำถามข้างต้น เราสามารถใช้หลักการของความน่าจะเป็นมาคำนวณได้ ดังตัวอย่างต่อไปนี้ ซึ่งอ้างอิงตารางความน่าจะเป็นที่แสดงไว้ข้างต้น ซึ่งมีข้อมูลสภาพอากาศแค่สองวัน


ตัวอย่างที่ 1 ถ้าวันนี้มีแดด โอกาสที่พรุ่งนี้จะมีแดด และ วันมะรืนจะฝนตกจะเป็นเท่าใด
เราสามารถแปลงโจทย์เป็นดังนี้
P(W3 = rainy, W2 = sunny | W1 = sunny)

ซึ่งจะมีค่าเท่ากับ
P(W3 = rainy | W2 = sunny, W1 = sunny) * P(W2 = sunny | W1 = sunny)

เมื่อเราใช้ การประมาณ Markov นิพจน์แรกก็จะถูกประมาณให้เหลือแค่ P(W3 = rainy | W2 = sunny) และค่าทั้งหมดก็จะเปลี่ยนเป็น
P(W3 = rainy | W2 = sunny) * P(W2 = sunny | W1 = sunny)

ซึ่งเมื่อแทนค่าจากตารางด้านบน จะได้คำตอบคือ 0.05 * 0.8 = 0.04
นั่นคือ ถ้าวันนี้มีแดด โอกาสที่พรุ่งนี้จะมีแดด และ วันมะรืนจะฝนตกจะเป็น 0.04

เราสามารถคิดอีกแบบ โดยใช้ state diagram ข้างต้นมาคำนวณ โดยคูณความน่าจะเป็นตามการเปลี่ยนสถานะดังรูป คือคูณเส้นสีแดง (พรุ่งนี้มีแดดเมื่อวันนี้มีแดด) กับเส้นสีน้ำเงิน (พรุ่งนี้ฝนตกเมื่อวันนี้มีแดด)


วันนี้ก็คงพอแค่นี้ก่อนนะครับ เดี๋ยวบทความถัดไปลองมาดูตัวอย่างเพิ่มเติมกัน

Tuesday, March 7, 2017

Thresholding โดยการหาค่า Threshold แบบอัตโนมัติ

ปกติเราจะต้องกำหนดค่า Threshold เพื่อทำ Thresholding ซึ่งตามความเป็นจริงถือว่ายากพอสมควร เพราะไม่รู้ว่าควรจะกำหนดค่านี้เป็นเท่าไหร่ดี เลยมีนักวิจัยคิดวิธีการที่จะคำนวณหาค่านี้โดยอัตโนมัติ และ OpenCV ได้นำมาใช้ด้วยกัน 2 วิธี คือ วิธีของ Otsu และ วิธี Triangle ลองไปอ่านหลักการกันได้ตามนี้ครับ
  • https://en.wikipedia.org/wiki/Otsu's_method
  • https://www.ncbi.nlm.nih.gov/pubmed/70454
ลองดูผลลัพธ์กันก่อน


ถ้าจะใช้งานสองวิธีนี้ใน OpenCV ก็ต้องเตรียม matrix ของรูปต้นฉบับให้เป็นแบบ CV_8UC1 หรือแบบ 8-bit 1 channel เสียก่อน (ใน reference บอกไว้) ดังนั้น เมื่อแปลง bitmap ให้เป็น Mat ด้วยคำสั่ง
Utils.bitmapToMat(bitmap, mat);

เมตริกซ์ mat ที่ได้จะเป็นแบบ CV_8UC4 โดยอัตโนมัติ เราจึงจำเป็นต้องแปลงให้เป็นแบบที่เราต้องการผ่านคำสั่ง
Imgproc.cvtColor(mat, mat1, Imgproc.COLOR_RGB2GRAY, 1);
จากนั้นค่อยมากำหนดการทำ thresholding โดยทั้งสองวิธีข้างต้นจะใช้ควบคู่กับการทำ thresholding 5 รูปแบบก่อนหน้านี้ เช่น ถ้าเราต้องการทำ binary thresholding โดยใช้ Otsu's method เพื่อกำหนดค่า threshold โดยอัตโนมัติก็จะใช้คำสั่ง
Imgproc.threshold(mat1, mat2, 0, 255, Imgproc.THRESH_BINARY | Imgproc.THRESH_OTSU);
ให้สังเกตการกำหนดค่าพารามิเตอร์จะพบว่า ค่า threshold เรากำหนดให้เป็น 0 เพราะว่าเดี๋ยววิธีของ Otsu จะคำนวณให้เอง ส่วนวิธีการทำ thresholding ก็จะเป็นสองแบบรวมกัน เลยใช้รูปแบบ Imgproc.THRESH_BINARY | Imgproc.THRESH_OTSU ครับ

โค้ดทั้งหมดก็จะประมาณนี้
xml

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:id="@+id/activity_main"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    tools:context="com.example.mobile.opencv102.MainActivity">

    <ImageView
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:id="@+id/ivImage"
        app:srcCompat="@drawable/lenna_gray"
        android:layout_alignParentTop="true"
        android:layout_centerHorizontal="true"
        android:layout_weight="1" />

    <RadioGroup
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:id="@+id/rgroup"
        android:layout_marginTop="24dp"
        android:layout_below="@+id/ivImage"
        android:layout_centerHorizontal="true">

        <RadioButton
            android:text="Original"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rOriginal"
            android:layout_weight="1"
            android:checked="true" />

        <RadioButton
            android:text="Binary Otsu"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rBinaryOtsu"
            android:layout_weight="1" />

        <RadioButton
            android:text="Binary Triangle"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rBinaryTriangle"
            android:layout_weight="1" />
    </RadioGroup>
</RelativeLayout>

java

import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.widget.ImageView;
import android.widget.RadioGroup;

import org.opencv.android.OpenCVLoader;
import org.opencv.android.Utils;
import org.opencv.core.CvType;
import org.opencv.core.Mat;
import org.opencv.imgproc.Imgproc;

public class MainActivity extends AppCompatActivity implements RadioGroup.OnCheckedChangeListener{
    private Bitmap bitmap, result;
    private ImageView ivImage;
    private RadioGroup rgroup;
    private Mat mat1, mat2;

    static {
        if(OpenCVLoader.initDebug()) {
            Log.i("OpenCV", "Success");
        }
        else {
            Log.i("OpenCV", "Fail");
        }
    }

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        ivImage = (ImageView) findViewById(R.id.ivImage);
        rgroup = (RadioGroup) findViewById(R.id.rgroup);
        rgroup.setOnCheckedChangeListener(this);

        //decode resource file to bitmap with no scale
        bitmap = BitmapFactory.decodeResource(getResources(), R.drawable.lenna_gray);


        //temporary matrix to get pixel values from bitmap
        Mat temp = new Mat();
        //convert bitmap to matrix, this matrix will always be of type CV_8UC4
        Utils.bitmapToMat(bitmap, temp);

        //source matrix, for Otsu and Triangle thresholding must be unsigned 8-bit 1 channel (gray)
        mat1 = new Mat(bitmap.getWidth(), bitmap.getHeight(), CvType.CV_8UC1);
        //convert temp matrix to mat1 of type CV_8U1, 1 channel
        Imgproc.cvtColor(temp, mat1, Imgproc.COLOR_RGB2GRAY, 1);

        //output matrix, grayscale 8-bit 1 channel
        mat2 = new Mat(bitmap.getWidth(), bitmap.getHeight(), CvType.CV_8UC1);

        //create bitmap having width (columns) and height(rows) as matrix and in the format of 8 bit/pixel
        result = Bitmap.createBitmap(mat2.cols(), mat2.rows(), Bitmap.Config.RGB_565);
    }

    @Override
    public void onCheckedChanged(RadioGroup radioGroup, int id) {
        if(id==R.id.rOriginal) {
            ivImage.setImageResource(R.drawable.lenna_gray);
            return;
        }
        else if(id==R.id.rBinaryOtsu) {
            Imgproc.threshold(mat1, mat2, 0, 255, Imgproc.THRESH_BINARY | Imgproc.THRESH_OTSU);
        }
        else if(id==R.id.rBinaryTriangle) {
            Imgproc.threshold(mat1, mat2, 0, 255, Imgproc.THRESH_BINARY | Imgproc.THRESH_TRIANGLE);
        }
        //convert result matrix to bitmap
        Utils.matToBitmap(mat2, result);
        //show bitmap in ImageView
        ivImage.setImageBitmap(result);
    }
}

Sunday, March 5, 2017

มาลอง Thresholding กัน

มาลองประมวลผลภาพอย่างง่ายต่อด้วยการทำ Thresholding ซึ่งก็คือการกำหนดค่า Threshold (มีทั้งแบบกำหนดเอง หรือได้จากการคำนวณโดยอัตโนมัติ) ที่มีค่าระหว่างช่วงค่าของพิกเซล 0-255 แล้วนำค่านี้ไปตัดสินใจสร้างรูปผลลัพธ์อีกที

ปกติแล้ว Thresholding มักจะใช้ในงาน segmentation คือแยกส่วนของภาพสีเทา ซึ่งมักจะแยกออกเป็นสองส่วนคือส่วนที่เราสนใจ (foreground) กับส่วนที่เราไม่สนใจ (background) ดังนั้นกระบวนการนี้จึงอาจถูกเรียกอีกชื่อว่า Binarization ก็ได้

ลองมาดูตัวอย่างผลลัพธ์ของการทำ Thresholding 5 แบบกันก่อนครับ
 


OpenCV มีคำสั่งในการทำ Thresholding คือ
public static double threshold(Mat src, Mat dst, double thresh, double maxval, int type)

-src และ dst คือ source และ destination matrix นั่นเอง
-thresh คือค่า threshold ที่เราเอาไว้แยกภาพ
-maxval คือค่าสูงสุดที่เราทำ thresholding แล้วอยากให้เป็น ปกติก็มักจะกำหนดให้เป็นค่าสูงสุดของภาพ เช่น 255
-type คือ วิธีการ thresholding มีด้วยกัน 7 แบบ ในที่นี้เราจะลอง 5 แบบ ได้แก่
(คัดลอกจาก http://docs.opencv.org/java/2.4.9/org/opencv/imgproc/Imgproc.html#threshold(org.opencv.core.Mat,%20org.opencv.core.Mat,%20double,%20double,%20int)

THRESH_BINARY
dst(x,y) = maxval if src(x,y) > thresh; 0 otherwise

THRESH_BINARY_INV
dst(x,y) = 0 if src(x,y) > thresh; maxval otherwise

THRESH_TRUNC
dst(x,y) = threshold if src(x,y) > thresh; src(x,y) otherwise

THRESH_TOZERO
dst(x,y) = src(x,y) if src(x,y) > thresh; 0 otherwise

THRESH_TOZERO_INV
dst(x,y) = 0 if src(x,y) > thresh; src(x,y) otherwise

ลองมาดูโค้ดกัน

xml (อาจจะดูแน่นไปหน่อยนะครับ)

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:id="@+id/activity_main"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    tools:context="com.example.mobile.opencv102.MainActivity">

    <ImageView
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:id="@+id/ivImage"
        app:srcCompat="@drawable/lenna_gray"
        android:layout_alignParentTop="true"
        android:layout_centerHorizontal="true"
        android:layout_weight="1" />

    <RadioGroup
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:id="@+id/rgroup"
        android:layout_alignParentBottom="true"
        android:layout_centerHorizontal="true">

        <RadioButton
            android:text="Original"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rOriginal"
            android:layout_weight="1"
            android:checked="true" />

        <RadioButton
            android:text="Binary"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rBinary"
            android:layout_weight="1" />

        <RadioButton
            android:text="Binary, Inverted"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rBinaryInverted"
            android:layout_weight="1" />

        <RadioButton
            android:text="Truncate"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rTruncate"
            android:layout_weight="1" />

        <RadioButton
            android:text="To zero"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rToZero"
            android:layout_weight="1" />

        <RadioButton
            android:text="To zero, Inverted"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rToZeroInverted"
            android:layout_weight="1" />
    </RadioGroup>

    <TextView
        android:text="Threshold"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:id="@+id/tvThreshold"
        android:textSize="18sp"
        android:layout_below="@+id/ivImage"
        android:layout_alignParentLeft="true"
        android:layout_alignParentStart="true"
        android:layout_marginTop="12dp" />

    <SeekBar
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:id="@+id/sbThreshold"
        android:layout_alignBottom="@+id/tvThreshold"
        android:layout_toRightOf="@+id/tvThreshold"
        android:layout_alignRight="@+id/ivImage"
        android:layout_alignEnd="@+id/ivImage"
        android:max="255"
        android:progress="127" />

</RelativeLayout>

java

package com.example.mobile.opencv102;

import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.widget.ImageView;
import android.widget.RadioGroup;
import android.widget.SeekBar;

import org.opencv.android.OpenCVLoader;
import org.opencv.android.Utils;
import org.opencv.core.CvType;
import org.opencv.core.Mat;
import org.opencv.imgproc.Imgproc;

public class MainActivity extends AppCompatActivity implements RadioGroup.OnCheckedChangeListener, SeekBar.OnSeekBarChangeListener{
    private Bitmap bitmap, result;
    private ImageView ivImage;
    private RadioGroup rgroup;
    private SeekBar sbThreshold;
    private Mat mat1, mat2;
    private int threshold = 127;
    private int type = -1;

    static {
        if(OpenCVLoader.initDebug()) {
            Log.i("OpenCV", "Success");
        }
        else {
            Log.i("OpenCV", "Fail");
        }
    }

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        ivImage = (ImageView) findViewById(R.id.ivImage);
        rgroup = (RadioGroup) findViewById(R.id.rgroup);
        rgroup.setOnCheckedChangeListener(this);
        sbThreshold = (SeekBar) findViewById(R.id.sbThreshold);
        sbThreshold.setOnSeekBarChangeListener(this);

        //decode resource file to bitmap with no scale
        bitmap = BitmapFactory.decodeResource(getResources(), R.drawable.lenna_gray);

        //source matrix, unsigned 8-bit 4 channels (RGBA)
        mat1 = new Mat(bitmap.getWidth(), bitmap.getHeight(), CvType.CV_8UC4);
        //convert bitmap to matrix
        Utils.bitmapToMat(bitmap, mat1);

        //output matrix, grayscale 8-bit 4 channels
        mat2 = new Mat(bitmap.getWidth(), bitmap.getHeight(), CvType.CV_8UC4);
        //create bitmap having width (columns) and height(rows) as matrix and in the format of 8 bit/pixel
        result = Bitmap.createBitmap(mat2.cols(), mat2.rows(), Bitmap.Config.RGB_565);
    }

    public void adjust(double thres, int type) {
        //thresholding
        //public static double threshold(Mat src, Mat dst, double thresh, double maxval, int type)
        Imgproc.threshold(mat1, mat2, thres, 255, type);

        //convert result matrix to bitmap
        Utils.matToBitmap(mat2, result);
        //show bitmap in ImageView
        ivImage.setImageBitmap(result);
    }

    @Override
    public void onCheckedChanged(RadioGroup radioGroup, int id) {
        if(id==R.id.rOriginal) {
            ivImage.setImageResource(R.drawable.lenna_gray);
            type = -1;
        }
        else if(id==R.id.rBinary) {
            type = Imgproc.THRESH_BINARY;
            adjust(threshold, type);
        }
        else if(id==R.id.rBinaryInverted) {
            type = Imgproc.THRESH_BINARY_INV;
            adjust(threshold, type);
        }
        else if(id==R.id.rTruncate) {
            type = Imgproc.THRESH_TRUNC;
            adjust(threshold, type);
        }
        else if(id==R.id.rToZero) {
            type = Imgproc.THRESH_TOZERO;
            adjust(threshold, type);
        }
        else if(id==R.id.rToZeroInverted) {
            type = Imgproc.THRESH_TOZERO_INV;
            adjust(threshold, type);
        }
    }

    @Override
    public void onProgressChanged(SeekBar seekBar, int progress, boolean fromUser) {
        threshold = progress;
        if(type!=-1) {
            adjust(threshold, type);
        }
    }

    @Override
    public void onStartTrackingTouch(SeekBar seekBar) {

    }

    @Override
    public void onStopTrackingTouch(SeekBar seekBar) {

    }
}

อ้างอิง
  • http://docs.opencv.org/3.2.0/db/d8e/tutorial_threshold.html
  • http://docs.opencv.org/java/2.4.9/org/opencv/imgproc/Imgproc.html#threshold(org.opencv.core.Mat,%20org.opencv.core.Mat,%20double,%20double,%20int)

Friday, March 3, 2017

Matrix Scaling กับ Point operation

Pixel processing อาจแบ่งได้ออกเป็น 2 แบบหลักๆ คือ ประมวลผลแต่ละพิกเซลของใครของมัน (ขอใช้ภาษาที่เข้าใจง่ายๆ :p ) หรือ point operation กับ การประมวลผลที่ต้องใช้พิกเซลข้างๆด้วย (Neighborhood operation)

ในที่นี้จะพูดถึง point operation ก่อน ซึ่งเราได้เจอมาแล้วในหัวข้อก่อนๆ เช่น การเปลี่ยนรูปสีให้เป็นรูปสีเทา หรือ การทำ image negative

หากเราต้องการประมวลผลแต่ละพิกเซล ในแต่ละ channel RGBA ส่วนใหญ่การประมวลผลก็จะอยู่ในรูปแบบ
output = alpha*input + beta

เมื่อ output คือเมตริกซ์ผลลัพธ์ และ input คือ เมตริกซ์ตั้งต้น ส่วน alpha และ beta ก็จะเป็นตัวคูณและตัวบวกเพิ่ม เราอาจเรียกการคำนวณนี้ว่า Matrix Scaling

เมื่อค่า alpha และ beta มีค่าต่างๆกัน จะให้ผลลัพธ์ดังตัวอย่างต่อไปนี้
  • alpha = 1 และ beta != 0 จะเป็นการเพิ่มหรือลดความสว่าง (brightness) ของรูป
  • alpha >0 และ beta = 0 จะเป็นการเพิ่มหรือลดค่า contrast ของรูป 
  • alpha = -1 และ beta = 255 เป็นการทำ image negative
ใน OpenCV เราสามารถใช้คำสั่ง
input.converTo(Mat output, int type, double alpha, double beta);

โดยที่ type ก็จะเป็นชนิดของเมตริกซ์ผลลัพธ์ที่ต้องการ เช่น CvType.CV_8UC4 เป็นต้น หรือกำหนดให้เป็นค่าติดลบเช่น -1 ก็ได้ ถ้าอยากให้เมตริกซ์ผลลัพธ์เป็นชนิดเดียวกับเมตริกซ์ตั้งต้น

ข้อดีของคำสั่งนี้ใน OpenCV คือมันจะปรับค่าของพิกเซลให้อยู่ในช่วง 0-255 โดยอัตโนมัติ

เราจะมาลองใช้คำสั่งนี้กันอีกครั้ง เพื่อปรับค่า brightness และ contrast ของรูป ดังนี้



โค้ดก็ประมาณนี้ครับ
xml

<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:app="http://schemas.android.com/apk/res-auto"
    xmlns:tools="http://schemas.android.com/tools"
    android:id="@+id/activity_main"
    android:layout_width="match_parent"
    android:layout_height="match_parent"
    android:paddingBottom="@dimen/activity_vertical_margin"
    android:paddingLeft="@dimen/activity_horizontal_margin"
    android:paddingRight="@dimen/activity_horizontal_margin"
    android:paddingTop="@dimen/activity_vertical_margin"
    tools:context="com.example.mobile.opencv102.MainActivity">

    <ImageView
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_alignParentTop="true"
        android:layout_centerHorizontal="true"
        android:id="@+id/ivImage"
        app:srcCompat="@drawable/lenna256" />

    <RadioGroup
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:layout_below="@+id/ivImage"
        android:layout_centerHorizontal="true"
        android:layout_marginTop="25dp"
        android:orientation="horizontal"
        android:id="@+id/rgroup">

        <RadioButton
            android:text="Origin"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rbtOrigin"
            android:layout_weight="1"
            android:checked="true" />

        <RadioButton
            android:text="Brightness"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rbtBright"
            android:layout_weight="1" />

        <RadioButton
            android:text="Contrast"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:id="@+id/rbtContrast"
            android:layout_weight="1" />

    </RadioGroup>

</RelativeLayout>

java

import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.widget.ImageView;
import android.widget.RadioGroup;

import org.opencv.android.OpenCVLoader;
import org.opencv.android.Utils;
import org.opencv.core.CvType;
import org.opencv.core.Mat;

public class MainActivity extends AppCompatActivity implements RadioGroup.OnCheckedChangeListener{
    private Bitmap bitmap;
    private ImageView ivImage;
    private RadioGroup rgroup;

    static {
        if(OpenCVLoader.initDebug()) {
            Log.i("OpenCV", "Success");
        }
        else {
            Log.i("OpenCV", "Fail");
        }
    }

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        ivImage = (ImageView) findViewById(R.id.ivImage);
        rgroup = (RadioGroup) findViewById(R.id.rgroup);
        rgroup.setOnCheckedChangeListener(this);
        //decode resource file to bitmap with no scale
        bitmap = BitmapFactory.decodeResource(getResources(), R.drawable.lenna256);
    }

    public void adjust(double alpha, double beta) {
        //source matrix, unsigned 8-bit 4 channels (RGBA)
        Mat mat1 = new Mat(bitmap.getWidth(), bitmap.getHeight(), CvType.CV_8UC4);
        //convert bitmap to matrix
        //Be careful that the output Mat have the same size as the input Bitmap
        //and of the 'CV_8UC4' type, RGBA format.
        Utils.bitmapToMat(bitmap, mat1);

        //output matrix, grayscale 8-bit 1 channel
        Mat mat2 = new Mat(bitmap.getWidth(), bitmap.getHeight(), CvType.CV_8UC3);
        //Method 1: use built-in class, fastest
        //increase brightness or contrast or both
        //out = alpha*(in) + beta
        mat1.convertTo(mat2, CvType.CV_8UC3, alpha, beta);

        //Method 2: single loop
        //it requires converting mat data type from byte to double
        //otherwise the mat.get() gives the wrong pixel value
//        mat1.convertTo(mat1, CvType.CV_64FC4);
//        //create temp arrays to keep pixels for both original and output
//        double[] source = new double[(int)(mat1.total()*mat1.channels())];
//        double[] dest = new double[(int)(mat2.total()*mat2.channels())];
//
//        //dump matrix to array
//        mat1.get(0, 0, source);
//        int j=0;
//        double alpha=1, beta=100;
//        //source RGBA, move every four bytes
//        for(int i=0;i<source.length;i+=4) {
//            //change brightness and contrast
//            dest[j] = alpha*source[i] + beta;
//            dest[j+1] = alpha*source[i+1] + beta;
//            dest[j+2] = alpha*source[i+2] + beta;
//            //dest RGB, mover every three bytes
//            j+=3;
//        }
//        //put the modified temp array to matrix, this step will clamp the pixel to <= 255
//        mat2.put(0, 0, dest);

        //create bitmap having width (columns) and height(rows) as matrix and in the format of 8 bit/pixel
        //ARGB_8888 and RGB565 are normal bitmap formats
        Bitmap result = Bitmap.createBitmap(mat2.cols(), mat2.rows(), Bitmap.Config.RGB_565);
        //convert result matrix to bitmap
        Utils.matToBitmap(mat2, result);
        //show bitmap in ImageView
        ivImage.setImageBitmap(result);
    }

    @Override
    public void onCheckedChanged(RadioGroup radioGroup, int id) {
        if(id==R.id.rbtOrigin) {
            ivImage.setImageResource(R.drawable.lenna256);
        }
        else if(id==R.id.rbtBright) {
            adjust(1,100);
        }
        else if(id==R.id.rbtContrast) {
            adjust(2,0);
        }
    }
}

Thursday, March 2, 2017

Lookup table และการวัดเวลาในการประมวลผลคำสั่ง

การทำ pixel processing สามารถใช้ lookup table เพื่อมาแก้ปัญหาได้ ตัว lookup table ก็คือตารางค่าที่มีการคำนวณไว้ล่วงหน้าแล้ว ถ้าสมมติว่าพิกเซลของรูปต้นฉบับมีค่าเท่าไหร่ เราก็สามารถเอาไปเทียบใน lookup table เพื่อหาผลลัพธ์ได้ทันที วิธีนี้ก็จะประหยัดเวลาในการคำนวณ โดยเฉพาะถ้าการคำนวณนั้นซับซ้อนไปได้มาก

ลองเทียบดูกับโจทย์ image negative ในตัวอย่างที่แล้ว เราต้องการคำนวณพิกเซลใหม่ โดย 255 - พิกเซลเก่า ซึ่งต้องทำทุกๆพิกเซล แต่เนื่องจากว่าพิกเซลมีค่าแค่ 256 ค่า คือจาก 0-255 ดังนั้น ถ้าสร้าง lookup table ไว้แบบนี้

index : 0       1      2       3    ... 255
value : 255  254  253  252  ...   0

ถ้าพิกเซลต้นฉบับมีค่าเป็น 0 ก็เอาไปเทียบในตารางข้างต้น จะได้ผลลัพธ์เป็น 255 ทันทีโดยไม่ต้องคำนวณ

สมมติว่ารูปมีขนาด 256x256 พิกเซล หรือทั้งหมด 65536 พิกเซล แทนที่จะคำนวณทุกพิกเซล ก็เหลือแค่การคำนวณเฉพาะ 256 พิกเซลใน lookup table ที่เหลือก็แค่เปรียบเทียบ ซึ่งจะประหยัดเวลาไปได้มาก

ดังนั้น โค้ดการใช้ lookup table กับปัญหา image negative ก็จะประมาณนี้

//need to convert original matrix to have the same type of output matrix
mat1.convertTo(mat1, CvType.CV_8UC3);
//create lookup matrix 1 row 256 columns (index 0-255)
Mat lookup = Mat.zeros(1, 256, CvType.CV_8UC1);
//an array of 256 members, index 0 is for pixel value 0
double[] temp = new double[256];
//loop to assign inverse to array
for(int i=0;i<256;i++) {
 temp[i] = 255-i;
}
//put array to lookup matrix
lookup.put(0, 0, temp);
//perform lookup table processing for all channels of mat1 and put result into mat2
Core.LUT(mat1, lookup, mat2);

แล้วเราจะทราบได้อย่างไรว่ามันใช้เวลาประมาณเท่าไหร่
หลักการก็ง่ายๆ วัดเวลาก่อน process กับหลัง process เสร็จ แล้วหาความต่างของเวลา ด้วยโค้ด

long tstart = System.nanoTime();
//------------------------
//our algorithm here
//------------------------
long tend = System.nanoTime();
double elapse = (tend-tstart)/1000000000.0;
Log.i("time", "Processing time = "+elapse+" seconds");

ผมลองวัดเวลาโดยประมาณของแต่ละวิธีในการทำ image negative ในมือถือที่ใช้ทดสอบ ได้ประมาณนี้ครับ
1. ใช้คำสั่ง
Core.bitwise_not(mat1, mat2);
ใช้เวลาเฉลี่ย 0.0072 วินาที

2. ใช้คำสั่ง
mat1.convertTo(mat2, CvType.CV_8UC3, -1, 255);
ใช้เวลาเฉลี่ย 0.027 วินาที

3. ใช้การวนลูปแถวและคอลัมน์ ใช้เวลาเฉลี่ย 3.35 วินาที

4. ใช้การ dump ไปประมวลผลใน array  ใช้เวลาเฉลี่ย 0.142 วินาที

5. ใช้ lookup table ข้างต้น  ใช้เวลาเฉลี่ย 0.0103 วินาที

เรียงตามลำดับความเร็ว คือ วิธีที่ 1 5 2 4 3

ลองพิจารณาดูแต่ละวิธี แล้วเลือกใช้งานตามความชอบเลยครับ ส่วนถ้าให้ผมเลือก ผมคงเลือกคำสั่งที่ OpenCV มีให้ก่อน เช่น วิธีที่ 1 หรือ 2 ถ้าใช้ไม่ได้ค่อยลองวิธี 5 4 และ 3 ตามลำดับครับ