Updates from June, 2017 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 9:36 pm on June 19, 2017 Permalink | Reply
    Tags:   

    Advanced Python: Coroutines 

    Coroutines are extremely powerful constructs that are often confused with generators. The difference between generator and coroutines: a generator only produces values, while a coroutine can also consume them.
    How coroutines works?

    • yield occurs and the generator pauses.
    • send() occurs from outside the function and the generator wakes up.
    • the value sent in assigned to the left side of the yield statement.
    • the generator continues processing until it encounters another yield statement.

    Let’s take two examples.

    1. Score board in 1-1 match.

    Suppose we want to make a score board for a basketball match between Houston and Golden State. There are multiple ways to do this, but let’s use coroutines.

    First we need to create a coroutine object.

    def tally():
        score = 0
        while True:
            increment = yield score
            score += increment
    

    Then we use it to update score of Houston and GoldenState

    houston = tally()
    next(houston) # return 0
    golden_state = tally()
    next(golden_state) # return 0
    

    Why call next? Whenever a ‘next’ call called on a coroutine object, the code inside is run until it meet the first yield statement, return the value on the right side of yield (which is score), pause and wait for the next call called.
    So the first two values to be printed out are two zeros.

    Then Houston just got 2 scores, right after that Golden State pay back with 3 scores

    houston.send(2) # return 2
    golden_state.send(3) # return 3
    

    Next, Houston continue with 2 scores and Golden State reply them with 2 scores

    houston.send(2) # return 4
    golden_state.send(2) # return 5
    

    The way that corountines work is: Whenever you call send method, it get the value that you send in, run the code until it meets the next yield statement, yield that value out and wait until the next send method is sent.
    So first houston’s score is 0, we call next, it returns 0. Then we send 2, it assigns 2 for increment, score increase 2, meet yield statement, and yield out score (2), pause there. Finally, we send 2, it assigns 2 for increment, score increase 2, meet yield statement, and yield out score again (now 4). Since yield is inside an infinite loop, it will run forever.

    2. Log file parser.
    Let’s say we have a log file with the content below.

    unrelated log messages
    sd 0:0:0:0 Attached Disk Drive
    unrelated log messages
    sd 0:0:0:0 (SERIAL=ZZ12345)
    unrelated log messages
    sd 0:0:0:0 [sda] Options
    unrelated log messages
    XFS ERROR [sda]
    unrelated log messages
    sd 2:0:0:1 Attached Disk Drive
    unrelated log messages
    sd 2:0:0:1 (SERIAL=ZZ67890)
    unrelated log messages
    sd 2:0:0:1 [sdb] Options
    unrelated log messages
    sd 3:0:1:8 (SERIAL=WW11111)
    unrelated log messages
    sd 3:0:1:8 [sdc] Options
    unrelated log messages
    XFS ERROR [sdc]
    unrelated log messages
    

    The task is: obtain the serial number of any drives that have XFS ERROR.

    We use regular expression for this task, so what we send to the coroutine is the pattern that the re module use to find matching values.

    Let’s define a function called get_serials, this function takes a file_name as an input, and it will return all the serial numbers of devices (or drives) that have XFS ERROR.

    import re
    def get_serials(file_name):
        ERROR_PAT = 'XFS ERROR ('\[sd[a-z]\])'
        matcher = match_regex(file_name, ERROR_PAT)
        device = next(matcher)
        while True:
            bus = matcher.send('(sd \S+) {}'.format(re.escape(device)))
            serial = matcher.send('{} \(SERIAL=([^)]*)\)'.format(bus))
            yield serial 
            device = matcher.send(ERROR_PAT)
    

    What is missing from the code above is match_regex function, we haven’t define it yet. It will be our coroutine object, we send it the pattern, it will return the string match the pattern.

    def match_regex(file_name, regex):
        with open(file_name) as f:
            lines = f.readlines()
        for line in reversed(lines):
            match = re.match(regex, line)
            if match:
                t = match.group()[0]
                regex = yield t 
    

    Here we read the log file in reversed order.
    Note it regex = yield t. First next call on match_regex inside get_serial will run the code inside match_regex, with the initialized pattern. It yields the result of the first matching line, which is XFS ERROR [sdc].
    Each iteration inside while of get_serials will get the serial number of the drive that has XFS Error. The first send call will send the pattern to get the drive’s bus, which is something like sd 2:0:0:1, then the serial will be found based on that bus value. It keeps repeating the process until nothing to be parsed.
    The returned values (serial numbers) are: WW11111, ZZ12345

    Those are two example that demo the usage of coroutines. In real life software development, we rarely see coroutines in action, but it still worth knowing.

     
  • loctv 6:41 pm on March 19, 2017 Permalink | Reply
    Tags: ,   

    Problem: Manasa and Stones 

    Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either a or b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

    Note: The numbers on the stones are in increasing order.

    Input Format

    The first line contains an integer T, i.e. the number of test cases. T test cases follow; each has 3 lines. The first line contains n (the number of stones). The second line contains a, and the third line contains b.

    Constraints

    1 <= T <= 10
    1 <= n, a, b <= 10^3

    Output Format

    Space-separated list of numbers which are the possible values of the last stone in increasing order.

    Sample Input

    2
    3 
    1
    2
    4
    10
    100
    

    Sample Output

    2 3 4 
    30 120 210 300 
    

    Explanation

    All possible series for the first test case are given below:

    1. 0,1,2
    2. 0,1,3
    3. 0,2,3
    4. 0,2,4

    Hence the answer 2 3 4.

    Series with different number of final steps for second test case are the following:

    1. 0, 10, 20, 30
    2. 0, 10, 20, 120
    3. 0, 10, 110, 120
    4. 0, 10, 110, 210
    5. 0, 100, 110, 120
    6. 0, 100, 110, 210
    7. 0, 100, 200, 210
    8. 0, 100, 200, 300

    Hence the answer 30 120 210 300.

    Approach:

    1. Using backtracking. Generate all possible sequences, get all last values, and put them into a set. This is acceptable with n small (less than 15), since the complexity is O(2^n). Here is the code for backtracking
    2. Analyze. Let’s take 2 examples above and find out the pattern. In the first example, n = 3 and there are 3 different ending values, max value is 4 and the difference from the largest to the smallest is 1 (4 -> 3 -> 2) . In the second example, n = 4 and there are 4 different ending values, max value is 300 and difference between pairs is 90. Have you seen the pattern yet? With n, there are n different values, the largest value is max(a,b)*(n-1), the difference is max(a,b) – min(a,b), or a – b, if a is bigger, otherwise b-a. How can we know that this pattern is the one that we’re looking for. First, since there are only two values a,b, assume a is bigger than b (it works the same way if b is bigger than a). Then the biggest possible value you can get is b*(n-1). since the first one is 0. The second biggest is b*(n-1) – (a-b), since this is the second biggest, the last value is b, instead of a. We c0ntinue this as long as the value return after calculate the difference is positive. And this is actually n-1 times, since we already manually calculate the largest.

    Source code. The chain function is how you print out all possible stones chain, with complexity O(2^n). Inside main is the code to solve this problem.

    def chain(n, arr, options):
        for i in options:
            arr[n] = arr[n-1] + i
            if n == len(arr) - 1:
                print(arr)
            else:
                chain(n+1, arr, options)
    
    def test():
        chain(1, [0]*4, (10, 100))
    
    if __name__ == '__main__':
        t = int(input().strip())
        for _ in range(t):
            n = int(input().strip())
            a = int(input().strip())
            b = int(input().strip())
            if b > a:
                a, b = b, a
            pos_values = [0]*n
            pos_values[0] = a*(n-1)
            for i in range(1, len(pos_values)):
                pos_values[i] = pos_values[i-1] - (a-b)
            pos_values = list(set(pos_values))
            print(*sorted(pos_values))
    
     
  • loctv 10:50 pm on March 7, 2017 Permalink | Reply
    Tags: ,   

    Problem: Check Mirror in N-ary tree 

    *Difficulty: Medium

    Given two n-ary tree’s the task is to check if they are mirror of each other or not.

    Example

    1                      1
    /    \                 /   \
    2      3             3     2

    Output: 1

    1                        1
    /  \                    /  \
    2    3                2     3

    Output: 0

    Note: you may assume that root of both the given tree as 1.

    Input:
    The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two space separated values n and e denoting the no of nodes and edges respectively. Then in the next line two lines are 2*e space separated values u,v denoting an edge from u to v for the both trees .

    Output:
    For each test case in a new line print 1 if both the trees are mirrors of each other else print 0.

    Constraints:
    1<=T<=20
    1<=n<=15
    1<=e<=20

    Example:
    Input:

    2
    3 2
    1 2 1 3
    1 3 1 2
    3 2
    1 2 1 3
    1 2 1 3
    Output:
    1
    0

    Approach: Since this is a N-arr tree, that means one node can have multiple child. So the easiest way is to consider it as a graph. Each graph has a list of adjacent nodes. The way to to check  if two threes (or graphs if you will) are mirror of each other or not is:

    1. They have the same number of nodes
    2. All node have the same number of adjacent nodes
    3. The child list of each node in the first tree when reversed will be exactly like the one in the node of second tree and vice versa.

    Implementation: Python 3

    def is_mirror(tree_1, tree_2):
        if len(tree_1) != len(tree_2):
            return False
        for node in tree_1:
            if len(tree_1[node]) != len(tree_2[node]):
                return False 
            if tree_1[node] != list(reversed(tree_2[node])):
                return False 
        return True 
    
    def create_tree():
        tree = {}
        arr = list(map(int, input().strip().split()))
        for i in range(0,len(arr),2):
            if arr[i] in tree:
                tree[arr[i]].append(arr[i+1])
            else:
                tree[arr[i]] = [arr[i+1]]
        return tree
    
    if __name__ == '__main__':
        t = int(input().strip())
        for _ in range(t):
            n, e = list(map(int, input().strip().split()))
            tree_1 = create_tree()
            tree_2 = create_tree()
            # print(tree_1)
            # print(tree_2)
            print(1 if is_mirror(tree_1, tree_2) else 0)
    
     
  • loctv 7:44 pm on February 27, 2017 Permalink | Reply
    Tags:   

    Thug life creator 

    Demo:

    Source code:

    https://github.com/MrNocTV/ThugLifeCreator

     

     
  • loctv 12:49 pm on February 22, 2017 Permalink | Reply
    Tags: ,   

    Problem: 

    *Difficulty: Easy

    Problem:

    ctci-find-the-running-median-english

    Approach:
    Since the constraints is so high, we need a way to insert and sort the array (or list) that has the complexity equal or lower than O(logn). With n loop and each loop costs O(logn) we have the complexity O(nlogn), which is acceptable. Using linked list and binary search is one of the possible ways. But If you know Python, this problem can be solved in 10 lines of code, using insort method from bisect module.

    Implementation: Python 3

    import bisect
    
    n = int(input())
    l = []
    for _ in range(n):
        ai = int(input())
        bisect.insort(l, ai)
        if len(l) % 2 == 0:
            print('%.1f' % ((l[len(l)//2-1]+l[len(l)//2])/2))
        else:
            print('%.1f' % (l[len(l)//2]))
    
     
  • loctv 11:46 pm on February 21, 2017 Permalink | Reply
    Tags: ,   

    Problem: Separate the Numbers 

    *Difficulty: Easy

    Problem:
    separate-the-numbers-english

    Approach:
    Here’s how I did it, and I think example is the best way to explain it:
    Example:
    s = 1011121314
    Start with first number = 1, next is 0, False
    Start with first number = 10, next is 11, next is 12, …..
    Eventually, return True
    The maximum length of first number will be equal len(s) // 2 (if length s is even), or len(s) // 2 + 1 (length s is odd)
    Let’s take another example:
    10000001000001
    First number: 1, next 0 => False
    First number: 10, next 00=> False
    First number: 100, next 000=>False
    First number: 1000. next 000=>False
    ….
    First number:1000000 next 1000001 => True
    Hope you get the idea :>

    Implementation: Python 3

    def is_beautiful(number):
        if number == '' or number[0] == '0' or len(number) <= 2:
            return [False] 
        bound = len(number) // 2
        start_length = 1
        while start_length <= bound:
            first_str = number[:start_length]
            first_int = int(first_str)
            i = start_length
            try:
                while i < len(number):
                    next = next_str(i, first_str, first_int, number)
                    if next is None:
                        break
                    else:
                        changed = False
                        next_1, next_2 = next
                        if int(next_1) == first_int+1:
                            first_str = next_1
                            first_int = int(next_1)
                            i += len(next_1)
                            changed = True 
                        else:
                            if next_2:
                                if int(next_2) == first_int+1:
                                    first_str = next_2
                                    first_int = int(next_2)
                                    i += len(next_2)
                                    changed = True 
                        # cant found next number 
                        if not changed:
                            break
                        # check out of bound 
                        if i > len(number):
                            break
                        # all numbers statisfy the condition
                        if i == len(number):
                            return True, number[:start_length]
            except Exception:
                pass
            start_length += 1
        return [False]
    
    def next_str(i, first_str, first_int , number):
        # get the next number 
        # check if it has equal or longer length 
        # return two next, but only one of them is usable 
        next_1 = ""
        next_2 = ""
        if i < len(number):
            if number[i] == '0':
                return None 
            else:
                if i + len(first_str) <= len(number):
                    next_1 = number[i:i+len(first_str)]
                if i + len(first_str) + 1 <= len(number):
                    next_2 = number[i:i+len(first_str)+1]
                return next_1, next_2
        return None
    
    def main():
        t = int(input())
        for _ in range(t):
            number = str(input().strip())
            result = is_beautiful(number)
            if result[0]:
                print('YES', result[1])
            else:
                print('NO')
    
    if __name__ == '__main__':
        main()
    
     
  • loctv 3:28 pm on February 20, 2017 Permalink | Reply
    Tags: ,   

    Problem: Making Anagrams 

    *Difficulty: Easy

    Problem:

    ctci-making-anagrams-english

    Approach: To be able to make anagrams from two string, we have to find their common characters first. For example, if we have abccd and cdcc, then their common characters is c and d. Then we build two string contains only character that is in both string a and string b. In the previous example, string a = ccd and string b = cdcc. The last thing we need to do is make them anagrams. We do that by iterating through either string a or string b, with each character d, if there are more d in string a than string b, we remove d from a to make the number of d equal in both a and b. In our example, string b will remove 1 ‘c’, then a = ccd and b = dcc. Notice that we don’t have to do this on string, we rather do this on dictionary of string. Since the input only contains lower English alphabet, the maximum size of the dictionary will contain only 26 keys and 26 corresponding values. If key ‘c’ in a has higher value than key ‘c’ in b, then set its value to ‘c’ in b.

    Implementation: Python 2.7

    from collections import Counter
    
    def make_anagrams(a, b):
        a_set = set(list(a))
        b_set = set(list(b))
        a_counter = Counter()
        b_counter = Counter()
        # get char in common 
        for c in a:
            if c in b_set:
                a_counter[c] += 1
        for c in b:
            if c in a_set:
                b_counter[c] += 1
        # make anagrams 
        for key in a_counter.keys():
            a_val = a_counter.get(key)
            b_val = b_counter.get(key)
            if a_val > b_val:
                a_counter[key] = b_val
            else:
                b_counter[key] = a_val
        # calculate removed char
        a_lost = len(a) - sum([a_counter.get(x) for x in a_counter.keys()])
        b_lost = len(b) - sum([b_counter.get(x) for x in b_counter.keys()])
        return a_lost + b_lost
    
    if __name__ == '__main__':
        a = input().strip()
        b = input().strip()
        print(make_anagrams(a, b))
    
     
  • loctv 10:25 pm on February 19, 2017 Permalink | Reply
    Tags: ,   

    Problem: Arrays Left Rotation 

    • Difficulty: Easy

    Problem description:
    Array Left Rotation pdf

    All approaching ideas is inspired by Python.
    Approach: The first thing come in my mind is using a for loop, using Python list slice notation. But it’s too expensive both in computing muscle and memory usage. With the constraints, it will get TLE. Another approach is using modular arithmetic. Basically, rotate array d times means that we start iterating at index d. We have to use modular arithmetic to wrap around the array in case of reaching the end of array but still haven’t iterated through all elements yet.

    Implementation: Python 3

    def rotate(arr, d):
        count = 0
        start = d % len(arr)
        while count < len(arr):
            print(arr[start], end=' ')
            count += 1
            start = (start + 1) % len(arr)
        print()
    
    if __name__ == '__main__':
        n, d = list(map(int, input().strip().split()))
        arr = list(map(int, input().strip().split()))
        rotate(arr, d)
    
     
  • loctv 9:16 pm on February 17, 2017 Permalink | Reply
    Tags: ,   

    Learn openCV3 (Python): Contours, Convex Contours, Bounding Rect, Min Area Rect, Min Enclosing Circle, Approximate Bounding Polygon. 

    Beside edges detection, contour detection is also one of the vital tasks in computer vision. One thing to notice here is that when find contours, we usually work with thresholded image. What is thresholding image? Just Google it, it’s simply putting a threshold value for pixels, if those pixels have value bigger than threshold value, they’re gonna be set to a new value.

    This is a very simple example, when we find contour in an image that have black background and a white rectangle in its center.

    First we create a 200×200 grayscale image having black background by using numpy.zeros method. Then we create a 100×100 white squares in that image. Next we threshold the image, every pixels that have values higher than 127 will be set to 255. Then we use opencv’s findContours() method to find all contours in the image. cv2.RETR_TREE basically means you want to get all contours. This method returns a tuple with 3 elements,  we only need to focus on the second one, contours. Keep in mind that findContours(), as well as many other methods in opencv, usually only work well with gray scale images. Finally we use drawContours() with green color to make all contours visible.

    import cv2
    import numpy as np 
    
    ESC = 27
    
    # create a black image with size 200x200 (in grayscale)
    img = np.zeros((200, 200), dtype=np.uint8)
    # set the center of image to be a 50x50 white rectangle
    img[50:150, 50:150] = 255 
    
    # threshold the image
    # if any pixels that have value higher than 127, assign it to 255
    ret, threshed_img = cv2.threshold(img, 127, 255, 0)
    
    # find contour in image
    # cv2.RETR_TREE retrieves the entire hierarchy of contours in image
    # if you only want to retrieve the most external contour
    # use cv.RETR_EXTERNAL
    image, contours, hierarchy = cv2.findContours(threshed_img, cv2.RETR_TREE,
                                cv2.CHAIN_APPROX_SIMPLE)
    # convert image back to BGR
    color_img = cv2.cvtColor(img, cv2.COLOR_GRAY2BGR)
    # draw contours onto image
    img = cv2.drawContours(color_img, contours, -1, (0, 255, 0), 2)
    
    cv2.imshow("contours", img)
    
    while True:
        keycode = cv2.waitKey()
        if keycode != -1:
            keycode &amp;= 0xFF
            if keycode == ESC:
                break
    
    cv2.distroyAllWindows
    

    Result:

    contours

    Next, we will see how to find a bounding box, minimum area rectangle, and minimum enclosing circle. (There is a tutorial on opencv website talking about this, you can check it out now or later)

    Let’s take this image as an example.

    image.CUOVVY.png

    You already know how to find contours in an image, so we won’t talk detailedly about that anymore. What we’re gonna talk about is finding bounding rect, min area rect, and enclosing circle of the ‘object’ in that image.

    First let’s write code to find contours .

    import cv2
    import numpy as np 
    
    # read and scale down image
    img = cv2.pyrDown(cv2.imread('hammer.jpg', cv2.IMREAD_UNCHANGED))
    
    # threshold image
    ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
                    127, 255, cv2.THRESH_BINARY)
    # find contours and get the external one
    image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL,
                    cv2.CHAIN_APPROX_SIMPLE)
    
    cv2.drawContours(img, contours, -1, (255, 255, 0), 1)
    
    cv2.imshow("contours", img)
    
    ESC = 27
    while True:
        keycode = cv2.waitKey()
        if keycode != -1:
            keycode &amp;= 0xFF
            if keycode == ESC:
                break
    cv2.destroyAllWindows()
    

    There is a different here. Instead of retrieving all contours, we only retrieve the outermost contour. Here’s the result:

    contour_external.png

    The contour wrap the ‘object’ is drawn in (255, 255, 0) color. The thickness is only 1, you can change the thickness by altering the last argument in cv2.drawContours().
    Here’s how cv2.RETR_TREE will look like:

    contour_tree.png

    It’s time to find the bounding rect, min area rect, and min enclosing circle.

    import cv2
    import numpy as np 
    
    # read and scale down image
    img = cv2.pyrDown(cv2.imread('hammer.jpg', cv2.IMREAD_UNCHANGED))
    
    # threshold image
    ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
                    127, 255, cv2.THRESH_BINARY)
    # find contours and get the external one
    image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_TREE,
                    cv2.CHAIN_APPROX_SIMPLE)
    
    # with each contour, draw boundingRect in green
    # a minAreaRect in red and
    # a minEnclosingCircle in blue
    for c in contours:
        # get the bounding rect
        x, y, w, h = cv2.boundingRect(c)
        # draw a green rectangle to visualize the bounding rect
        cv2.rectangle(img, (x, y), (x+w, y+h), (0, 255, 0), 2)
    
        # get the min area rect
        rect = cv2.minAreaRect(c)
        box = cv2.boxPoints(rect)
        # convert all coordinates floating point values to int
        box = np.int0(box)
        # draw a red 'nghien' rectangle
        cv2.drawContours(img, [box], 0, (0, 0, 255))
    
        # finally, get the min enclosing circle
        (x, y), radius = cv2.minEnclosingCircle(c)
        # convert all values to int
        center = (int(x), int(y))
        radius = int(radius)
        # and draw the circle in blue
        img = cv2.circle(img, center, radius, (255, 0, 0), 2)
    
    print(len(contours))
    cv2.drawContours(img, contours, -1, (255, 255, 0), 1)
    
    cv2.imshow("contours", img)
    
    ESC = 27
    while True:
        keycode = cv2.waitKey()
        if keycode != -1:
            keycode &amp;= 0xFF
            if keycode == ESC:
                break
    cv2.destroyAllWindows()
    

    Use cv2.boundingRect to get the bounding rectangle (in green), cv2.minAreaRect to get the minimum area rectangle (in red), and cv2.minEnclosingCircle to get minimum enclosing circle (in blue).

    Result:

    contour_all.png
    More on contours, convex hull.

    import cv2
    import numpy as np 
    
    # downscale and read image
    img = cv2.pyrDown(cv2.imread('hammer.jpg', cv2.IMREAD_UNCHANGED))
    # threshold image
    ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
                        127, 255, cv2.THRESH_BINARY)
    # get contours from image
    image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL,
                        cv2.CHAIN_APPROX_SIMPLE)
    
    # for each contour
    for cnt in contours:
        # get convex hull
        hull = cv2.convexHull(cnt)
        # draw it in red color
        cv2.drawContours(img, [hull], -1, (0, 0, 255), 1)
    
    cv2.imshow("contours", img)
    
    ESC = 27
    while True:
        keycode = cv2.waitKey(25)
        if keycode != -1:
            keycode &amp;= 0xFF
            if keycode == ESC:
                break
    
    cv2.destroyAllWindows()
    

    Result:

    convex_hull.png

    With the demonstration, you can figure out what ‘convex hull’ is.

    Visit OpenCV Website to get more information as well as example code about contours.

    More about opencv drawing functions

    Besides convex hull, there is one more thing you need to know is ‘approximate polygon’. I consider an approximate polygon is a basic shape of an object. In OpenCV, approximate bounding polygon can be calculated by using cv2.approxPolyDP. This method use Douglas-Peucker algorithm.

    import numpy
    import cv2 
    
    # read and downscale image
    img = cv2.pyrDown(cv2.imread('hammer.jpg', cv2.IMREAD_UNCHANGED))
    # threshold image
    # this step is neccessary when you work with contours
    ret, threshed_img = cv2.threshold(cv2.cvtColor(img, cv2.COLOR_BGR2GRAY),
                            127, 255, cv2.THRESH_BINARY)
    # find contours in image
    image, contours, hier = cv2.findContours(threshed_img, cv2.RETR_EXTERNAL,
                            cv2.CHAIN_APPROX_SIMPLE)
    
    for cnt in contours:
        # calculate epsilon base on contour's perimeter
        # contour's perimeter is returned by cv2.arcLength
        epsilon = 0.01 * cv2.arcLength(cnt, True)
        # get approx polygons
        approx = cv2.approxPolyDP(cnt, epsilon, True)
        # draw approx polygons
        cv2.drawContours(img, [approx], -1, (0, 255, 0), 1)
    
        # hull is convex shape as a polygon
        hull = cv2.convexHull(cnt)
        cv2.drawContours(img, [hull], -1, (0, 0, 255))
    
    cv2.imshow('contours', img)
    ESC = 27
    
    while True:
        keycode = cv2.waitKey()
        if keycode != -1:
            keycode &amp;= 0xFF
            if keycode == ESC:
                break
    
    cv2.destroyAllWindows()
    

    Result:

    ssssss.png

     

    The approx bounding polygon is in green, and the convex hull is in red.

    Again, you can find code example on OpenCV website, I post this because I want to share what I’ve learn. My explanations might be different than things that you get on opencv website, so you will not read the same thing twice.

     
  • loctv 12:06 pm on February 16, 2017 Permalink | Reply
    Tags: ,   

    Learn OpenCV3 (Python): Simple Image Filtering 

    In image filtering, the two most basic filters are LPF (Low Pass Filter) and HPF(High Pass Filter).
    LPF is usually used to remove noise, blur, smoothen an image.
    Whereas HPF is usually used to detect edges in an image.
    Both LPF and HPF use kernel to filter an image.
    A kernel is a matrix contains weights, which always has an odd size (1,3,5,7,..).
    In case of LPF, all values in kernel sum up to 1. If the kernel contains both negative and positive weights, it’s probably used to sharpen (or smoothen) an image. Example

    kernel_3x3 = numpy.array([
        [-1, -1, -1],
        [-1,  9, -1],
        [-1, -1, -1]
    ])
    

    If the kernel contains only positive weights and sum up to 1, it’s used to blur an image. Example

    kernel = numpy.array([
        [0.04, 0.04, 0.04, 0.04, 0.04],
        [0.04, 0.04, 0.04, 0.04, 0.04],
        [0.04, 0.04, 0.04, 0.04, 0.04],
        [0.04, 0.04, 0.04, 0.04, 0.04],
        [0.04, 0.04, 0.04, 0.04, 0.04]
    ])
    # or you can use nump.ones
    kernel = numpy.ones((5, 5), numpy.float32) / 25
    

    The last line of code in the example above can be visualize in this picture:

    screenshot-from-2017-02-16-11-30-06

    It first creates a 5×5 matrix with all weights 1, and then divides 25 to make all the weights sum up to 1.

    In case of HPS, the kernel contains both negative and positive weights, sum up to 0. Example

    kernel_3x3 = numpy.array([
        [-1, -1, -1],
        [-1,  8, -1],
        [-1, -1, -1]
    ])
    

    These are three most basic and common kernels. You can create a kernel with left side is positive weights and right side is negative weights to make a new effect.

    Now we’ve known about LPS, FPS and kernel. Let’s apply them with OpenCV.
    A kernel is applied on an image with an operation call ‘convolve’.  There are multiple ways to convolve an image with a kernel.

    • scipy.ndimage.convolve(img, kernel)
    • cv2.filter2D(src_image, channel_depth, kernel, dst_image)

    Examples:

    import scipy.ndimage
    import cv2
    import numpy as np
    
    # create a 3x3 kernel
    kernel_3x3 = np.array([
        [-1, -1, -1],
        [-1,  8, -1],
        [-1, -1, -1]
    ])
    # create a 5x5 kernel
    kernel_5x5 = np.array([
        [-1, -1, -1, -1, -1],
        [-1,  1,  2,  1, -1],
        [-1,  2,  4,  2, -1],
        [-1,  1,  2,  1, -1],
        [-1, -1, -1, -1, -1]
    ])
    
    # read image in grayscale
    img = cv2.imread("screenshot.png", cv2.IMREAD_GRAYSCALE)
    
    # convolve image with kernel
    k3 = scipy.ndimage.convolve(img, kernel_3x3)
    k3_1 = cv2.filter2D(img, -1, kernel_3x3)
    k5 = scipy.ndimage.convolve(img, kernel_5x5)
    k5_1 = cv2.filter2D(img, -1, kernel_5x5)
    
    # show images
    cv2.imshow("3x3", k3)
    cv2.imshow("5x5", k5)
    cv2.imshow("3x3_1", k3_1)
    cv2.imshow("5x5_1", k5_1)
    
    # wait for ESC to be pressed
    ESC = 27
    while True:
        keycode = cv2.waitKey(25)
        if keycode != -1:
            keycode &= 0xFF
            if keycode == ESC:
                break
    
    cv2.destroyAllWindows()
    

    Result:

    3x3

    3×3

    3x3_1

    3x3_1

    5x5

    5×5

    5x5_1

    5x5_1

    As you can see, the result is very different between cv2.filter2D and scipy.ndarray.convolve.

    One last example I want to show you is stroking edges in an image. This involve bluring (using cv2.medianFilter), finding edge (using cv2.Laplacian), normalize and inverse image.

    import cv2
    import numpy as np
    
    def strokeEdge(src, dst, blurKSize = 7, edgeKSize = 5):
        # medianFilter with kernelsize == 7 is expensive
        if blurKSize >= 3:
            # first blur image to cancel noise
            # then convert to grayscale image
            blurredSrc = cv2.medianBlur(src, blurKSize)
            graySrc = cv2.cvtColor(blurredSrc, cv2.COLOR_BGR2GRAY)
        else:
            # scrip blurring image
            graySrc = cv2.cvtColor(src, cv2.COLOR_BGR2GRAY)
        # we have to convert to grayscale since Laplacian only works on grayscale images
        # then we can apply laplacian edge-finding filter
        # cv2.CV_8U means the channel depth is first 8 bits
        cv2.Laplacian(graySrc, cv2.CV_8U, graySrc, ksize=edgeKSize)
        # normalize and inverse color
        # making the edges have black color and background has white color
        normalizedInverseAlpha = (1.0 / 255) * (255 - graySrc)
        channels = cv2.split(src)
        # multiply normalized grayscale image with source image
        # to darken the edge
        for channel in channels:
            channel[:] = channel * normalizedInverseAlpha
        cv2.merge(channels, dst)
    

    Result:

    screenshot

    increase ksize of median and Laplacian you will get something like this:

    screenshot

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel