## Tagged: Tutorial Toggle Comment Threads | Keyboard Shortcuts

• ## Topological Sort and Tasks Scheduling (Kahn’s algorithm)

Topological Sort of a directed graph (a graph with unidirectional edges) is a linear ordering of its vertices such that for every directed edge (U, V) from vertex U to vertex VU comes before V in the ordering.

Given a directed graph, find the topological ordering of its vertices.

Example 1:

Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1]
Output: Following are the two valid topological sorts for the given graph:
1) 3, 2, 0, 1
2) 3, 2, 1, 0 Example 2:

Input: Vertices=5, Edges=[4, 2], [4, 3], [2, 0], [2, 1], [3, 1]
Output: Following are all valid topological sorts for the given graph:
1) 4, 2, 3, 0, 1
2) 4, 3, 2, 0, 1
3) 4, 3, 2, 1, 0
4) 4, 2, 3, 1, 0
5) 4, 2, 0, 3, 1 Here are a few fundamental concepts related to topological sort:

1. Source: Any node that has no incoming edge and has only outgoing edges is called a source.
2. Sink: Any node that has only incoming edges and no outgoing edge is called a sink.
3. So, we can say that a topological ordering starts with one of the sources and ends at one of the sinks.
4. A topological ordering is possible only when the graph has no directed cycles, i.e. if the graph is a Directed Acyclic Graph (DAG). If the graph has a cycle, some vertices will have cyclic dependencies which makes it impossible to find a linear ordering among vertices.

To find the topological sort of a graph we can traverse the graph in either a Breadth First Search (BFS) way using Kahn’s algorithm or Depth First Search (DFS). We will start with all the sources, and in a stepwise fashion, save all sources to a sorted list. We will then remove all sources and their edges from the graph. After the removal of the edges, we will have new sources, so we will repeat the above process until all vertices are visited.

[preserved_text 1fbfd1112ea81554cf8bd39aca16ff45 /]

#### Time Complexity

In step ‘d’, each vertex will become a source only once and each edge will be accessed and removed once. Therefore, the time complexity of the above algorithm will be O(V+E), where ‘V’ is the total number of vertices and ‘E’ is the total number of edges in the graph.

#### Space Complexity

The space complexity will be O(V+E), since we are storing all of the edges for each vertex in an adjacency list.

There are ‘N’ tasks, labeled from ‘0’ to ‘N-1’. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, find out if it is possible to schedule all the tasks.

Example 1:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2]
Output: true
Explanation: To execute task '1', task '0' needs to finish first. Similarly, task '1' needs to finish
before '2' can be scheduled. A possible scheduling of tasks is: [0, 1, 2]


Example 2:

Input: Tasks=3, Prerequisites=[0, 1], [1, 2], [2, 0]
Output: false
Explanation: The tasks have cyclic dependency, therefore they cannot be scheduled.

As you can see, we can represent the task and its dependency as an edge in a directed graph. There’s a little change in the above code that need to be changed to solve this problem so I let this as an exercise for you. Instead of returning a list, you just need to return a boolean.

Another application of Topological Sort is to check if a directed graph contains a cycle.

• ## Folk/Join Framework & Merge Sort (Java)

We all know that Merge Sort is one of the fastest sorting algorithms out there (on average), it’s based on the divided & conquer technique. In today world of computing, computers usually have more than one CPU, and to take advantage of all of those resources, we need to implement Merge Sort in a way such that it will leverage all of those juicy CPUs.

Today I am going to show you how to implement Merge Sort using Java’s Folk/Join framework. However before we start, let’s get some information about Folk/Join framework in Java.

So what is Folk/Join framework?

This framework is based on the ForkJoinPool class in Java, which is a special kind of executor, two operations, the fork() and join() methods (and their different variants), and an internal algorithm named the work-stealing algorithm. What this algorithm does is to determine which tasks to be executed. When a task is waiting for the finalization of a child task using the join() method, the thread that is executing that task steal another task from the pool of tasks that are waiting and starts its execution. There are disadvantages though, for example, it wont work if the child task is doing some IO operations.

From Java 8 onward, with the introduction of the mighty Stream, behind the scene, it is implemented using Fork/Join framework.

if ( problem.size() > DEFAULT_SIZE) {
} else {
}


The above snippet is basically what it looks like. It’s very similar to your normal recursive function, we have a base case, in this case the data is small enough for us to calculate directly, otherwise we will split the data into two equal parts, and continue to process recursively on each part.

Similarly, the Merge Sort algorithm stops when the data need to be processed is small enough (usually just 1 element).

Here’s one of the way you can implement a normal Merge Sort.

public class SerialMergeSort {

public void mergeSort (Comparable data[], int start, int end) {
if (end-start > 1) {
int middle = (end + start) >>> 1;
mergeSort(data,start,middle);
mergeSort(data,middle,end);
merge(data,start,middle,end);
}
}

private void merge(Comparable[] data, int start, int middle, int end) {
int length=end-start;
Comparable[] tmp=new Comparable[length];

int i, j, index;
i=start;
j=middle;
index=0;

while ((i<middle) && (j<end)) {
if (data[i].compareTo(data[j])<=0) {
tmp[index]=data[i++];
} else {
tmp[index]=data[j++];
}
index++;
}

while (i<middle) {
tmp[index++]=data[i++];
}

while (j<end) {
tmp[index++]=data[j++];
}

for (index=0; index < length; index++) {
data[index+start]=tmp[index];
}
}
}


With Fork/Join framework, most of the time you will choose between RecursiveAction which does not return anything and RecursiveTask which is a generic abstract class which returns something when it’s done. With Merge Sort, we need to do an extract processing step when two child tasks are done (merge the sorted lists). In this case our class will extend CountedCompleter class. It has some important methods that we’re going to use.

• compute(): this is where the body of the Merge Sort algorithm is implemented.
• addToPendingCount(1): Increase the number of child tasks by 1 that need to be completed before onCompletion method can be executed.
• onCompletion(CountedComplete caller): this method will be called as soon as all of the child tasks are finished.
• tryComplete(): tell the parent task that one of its child tasks has been completed.

Here is the most important part in the compute() method:

@Override
public void compute() {
if (end - start >= 1024) {
middle = (end + start) >>> 1;
} else {
new SerialMergeSort().mergeSort(data, start, end);
tryComplete();
}
}


Let’s explain the code snippet above.

As you can see, it’s very similar to the serial Merge Sort. We use theSerialMergeSort for the base case. Also we add the reference to the parent task in case we need it. tryComplete() internally will call onCompletion(), when onCompletion() is finished it will call tryComplete() over its parent to try to complete that task.

If the data is still too big (more than 1024 elements), we will split it into two child MergeSortTask, addToPendingCount(1) to register this as one of the child task of the parent task. Then we call fork() to asynchronously invoke task1 and task2.

Here’s the onCompletion() part that you’re looking for:

	@Override
public void onCompletion(CountedCompleter caller) {

if (middle == 0) {
return;
}
int length = end - start ;
Comparable tmp[] = new Comparable[length];

int i, j, index;
i = start;
j = middle;
index = 0;

while ((i < middle) && (j < end)) {
if (data[i].compareTo(data[j]) <= 0) {
tmp[index] = data[i++];
} else {
tmp[index] = data[j++];
}
index++;
}

while (i < middle) {
tmp[index++] = data[i++];
}

while (j < end) {
tmp[index++] = data[j++];
}

for (index = 0; index < length; index++) {
data[index + start] = tmp[index];
}

}


It's the "merge" part of the SerialMergeSort.

It’s already too long for a daily blog post and I’m also not a fan of a blog that’s too long. After running benchmark locally on my local laptop (4 cores – 8 threads), the improvement in term of time is usually more than x2 on average.

• ## 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: 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. 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

# 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: 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: 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

# 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
# convert all values to int
center = (int(x), int(y))
# 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: More on contours, convex hull.

import cv2
import numpy as np

# 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: With the demonstration, you can figure out what ‘convex hull’ is.

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

# 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: 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.

• #### Ronald Wahome 1:01 am on November 9, 2017 Permalink | Reply

Really well explained better than the documentation as far as the approxPolyDP function goes. Thanks!

• ## 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: 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]
])

# 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: 3×3 3x3_1 5×5 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: increase ksize of median and Laplacian you will get something like this: • ## Learn OpenCV (Python): Basic Video Operations

System information:

• Ubuntu: 16.04
• Opencv: 3.1.0

To work with video in opencv, you just only need to care about these two attributes:

• cv2.VideoCapture(video_path)
• cv2.VideoWriter(video_path, codec, fps, size, is_color)

About codec, depends on operating system you have, choose the appropriate one:

• In Fedora (Linux): DIVX, XVID, MJPG, X264, WMV1, WMV2
• In Windows: DIVX
• In OS X: Dunno :V

Depends on what video codec you use, different file extension will be supported.
You can read more here .

import numpy as np
import cv2

ESCAPE_KEY = 27
# capture video
video_capture = cv2.VideoCapture('/home/loctv/Python/cv/data/pycv-master/first_edition/chapter2/miscellaneous/MyInputVid.avi')

# while video has not been released yet (or still opened)
while video_capture.isOpened():
# read video frame by frame
# convert to gray image
gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
# display
cv2.imshow("frame", gray)

# wait to press 'ESC' key
# 27 means every 27 ms, this if block will be called again
# you can alter this to change FPS (Frame Per Second)
if cv2.waitKey(27) == ESCAPE_KEY:
break

# close video stream
video_capture.release()
# as it describes, destroy all windows has been opened by opencv
cv2.destroyAllWindows()

• Write Video
import cv2

# 'capture' video
videoCapture = cv2.VideoCapture('MyInputVid.avi')
# set frame per second
fps = videoCapture.get(cv2.CAP_PROP_FPS)
# size of the copied video
size = (
int(videoCapture.get(cv2.CAP_PROP_FRAME_WIDTH)),
int(videoCapture.get(cv2.CAP_PROP_FRAME_HEIGHT))
)
# create video writer
# video codec = WMV1
# you can try others video codec
videoWriter = cv2.VideoWriter(
'MyOutputVid.avi', cv2.VideoWriter_fourcc(*"WMV1"), fps, size
)

# loop until there is no more frame
while success:
# write frame by frame
videoWriter.write(frame)

• Capture camera frames
import numpy as np
import cv2

ESCAPE_KEY = 27
# capture  frame from camera (webcam)
# 0 is the index to specify which camera you want to capture
# in this case, there only one camera
camera_capture = cv2.VideoCapture(0)

# # read the first frame
# while still more frame to read
while success:
# display frame
# if you want you can convert frame from BGR to gray-scale
# for faster processing
cv2.imshow("frame", frame)

# 25 means this if block will be called every 25 ms
# help the frames displayed slow enough to be processed
# wait for 'ESC' key to be pressed
# then program will be stoped
if cv2.waitKey(25) == ESCAPE_KEY:
break

# turn off webcam (by releasing capturer)
camera_capture.release()
cv2.destroyAllWindows()

• Capture camera frames and writer to file
import numpy as np
import cv2

ESCAPE_KEY = 27
# capture  frame from camera (webcam)
# 0 is the index to specify which camera you want to capture
# in this case, there only one camera
camera_capture = cv2.VideoCapture(0)
# roughly estimate fps
fps = 25
# size of new video will be the same size with capture frames
size = (
int(camera_capture.get(cv2.CAP_PROP_FRAME_WIDTH)),
int(camera_capture.get(cv2.CAP_PROP_FRAME_HEIGHT))
)
# set video codec
# after trying several video codecs
# this one works for me
# if it does not work, let's try another one
fourcc = cv2.VideoWriter_fourcc(*"MJPG")
# create video writer object
video_writer = cv2.VideoWriter(
'CameraCapture.avi', fourcc, fps, size
)

# # read the first frame
# while still more frame to read
while success:
# instead of displaying frame like we did before
# write it to file
video_writer.write(frame)
cv2.imshow("frame", frame)

# 25 means this if block will be called every 25 ms
# help the frames displayed slow enough to be processed
# wait for 'ESC' key to be pressed
# then program will be stoped
if cv2.waitKey(25) == ESCAPE_KEY:
break

# turn off webcam (by releasing capturer)
camera_capture.release()
# and release video writer
# video_writer.release()
cv2.destroyAllWindows()


‘The number of camera and their order is system dependently, but opencv does not give us any way to query the number of cameras or their order. Fortunately, we can use VideoCapture‘s method isOpened() to check if we successfully connect to a real camera.

• Work with multiple cameras:

In the examples above, you can use read() method of VideoCapture to read frames of one camera, but it cant be use for reading frame of multiple cameras. In that case, you have to use grab() and retrieve():
Suppose you already have two camera capture object for two camera

success_0 = camera_capture_0.grab()
success_1 = camera_capture_1.grab()
while success_0 and success_1:
frame_0 = camera_capture_0.retrieve()
frame_1 = camera_capture_1.retrieve()


Those are basic operations that opencv supports for video reading and writing.

• ## Learn OpenCV (Python): Basic image manipulations / Operations

System information:

• OS: Ubuntu 16.04
• OpenCV: 3.1.0
• Convert Array to Image
import numpy
import os
import cv2

random_byte_array = bytearray(os.urandom(120000))
# or random_byte_array = numpy.random.randint(0, 256, 120000)
flat_numpy_array = numpy.array(random_byte_array)

# reshape to an grayscale image with 300px in height, 400px in width
# which is a 2D array
gray_image = flat_numpy_array.reshape(300, 400)
cv2.imwrite('../data/random_gray.png', gray_image)

# reshape to an BGR image with  100px in heigth, 400px in width
# and 3 channels (BGR)
# which is a 3D array
bgr_image = flat_numpy_array.reshape(100, 400, 3)
cv2.imwrite('../data/random_bgr.png', bgr_image)

# *Note: this is only an example, the paths is not necessarily to be
# the same on your system

• Change pixel values in gray-scale image
import numpy as np
import cv2
import random
import datetime

# seed the current time for random every time program starts
random.seed(datetime.datetime.now())
ESCAPE_KEY = 27

# read image and change to gray scale
# img.shapre on a gray-scale image return (row, col)
row_count, column_count = img.shape

# change all pixels value to random value from 0-255
for i in xrange(row_count):
for j in xrange(column_count):
img[i, j] = random.randint(0, 255)

# show image with title "show"
cv2.imshow("show", img)

# pause the program
# if you remove this if block
# the window will close immediately after the program starts
# causing you see nothing
if cv2.waitKey() == ESCAPE_KEY:
cv2.destroyAllWindows()

• Change pixel values in BGR image (in open cv, BGR = RGB, weird!)
import numpy as np
import cv2
import random
import datetime

ESCAPE_KEY = 27
# seed every time start a new program
random.seed(datetime.datetime.now())

# with color image, img.shape returns (row, column, channels)
row, column, channels = img.shape

# change all pixels to random value
for i in xrange(row):
for j in xrange(column):
B_random = random.randint(0, 255)
G_random = random.randint(0, 255)
R_random = random.randint(0, 255)
img[i, j] = [B_random, G_random, R_random]

# show image
cv2.imshow("Image", img)

# press ESC key to exit
if cv2.waitKey() == ESCAPE_KEY:
cv2.destroyAllWindows()


But changing pixel values by indexing is not an appropriate way to do, instead using item (to retrieve value) and itemset (to change pixel value) method.

import numpy as np
import cv2

ESCAPE_KEY = 27
# B, G, R = 0, 1, 2 respectively
B, G, R = 0, 1, 2

# img.shape return (row, col, channels)
row, col, channels = img.shape

# for example
# we want to set all B values of each pixel to 0
# itemset((i, j, channel), new_val), channel could be B, G, R (or 0, 1, 2)
for i in xrange(row):
for j in xrange(col):
new_val = 0
img.itemset((i, j, B), new_val)

# show image
cv2.imshow("Tittle", img)

if cv2.waitKey() == ESCAPE_KEY:
cv2.destroyAllWindows()


Here’s how you can change all pixel values without for loop, using numpy array syntax.

import cv2
import numpy as np
import random
import datetime

ESCAPE_KEYS = 27
random.seed(datetime.datetime.now())
B, G, R = 0, 1, 2

# change all pixels in original image to a random color
# create a solid-random-color image
B_random = random.randint(0, 255)
G_random = random.randint(0, 255)
R_random = random.randint(0, 255)
img[:, :] = [B_random, G_random, R_random]

# or change only channel B to random value
img[:, :, B] = B_random
# or change channels B, G to random value
img[:, :, (B, G)] = (B_random, G_random)
# or change all three channels
# this have the same effect with line 17
img[:, :, (B, G, R)] = (B_random, G_random, R_random)
cv2.imshow("show", img)
if cv2.waitKey() == ESCAPE_KEYS:
cd2.destroyAllWindows()

• Copy a portion of an image, and place it overlap to other portion

The code below copy all pixel values in a 100×100 portion, starting index (0,0) and place overlap it on portion with starting index (300, 300)

import numpy as np
import cv2

ESCAPE_KEY = 27

# get 100x100 portion with starting index at (0, 0)
# and place it overlap portion with starting index at (300, 300)
my_roi = img[0:100, 0:100]
img[300:400, 300:400] = my_roi

cv2.imshow("show", img)
if cv2.waitKey() == ESCAPE_KEY:
cv2.destroyAllWindows()


• ## Fix: ‘pymysql.err.OperationalError: (2003 ‘ on Ubuntu 16.04

I’ve been learning web scraping with Python, and try using pymysql package.
Here’s the script:

import pymysql
# connect with mysql
conn = pymysql.connect(host='127.0.0.1', unix_socket='/tmp/mysql.sock',
user='root', passwd='02390128', db='mysql')
cur = conn.cursor()
cur.execute("USE scraping;")
cur.execute("SELECT * FROM pages WHERE id=1")
print(cur.fetchone())
cur.close()
conn.close()


I run this script through terminal command:

python xxx.py


and getting this error:

Traceback (most recent call last):
File "ConnectMYSQL.py", line 4, in <module>
user='root', passwd=None, db='mysql')
File "/home/loctv/Documents/Python/WebCrawling/scarpingEnv/local/lib/python2.7/site-packages/PyMySQL-0.6.2-py2.7.egg/pymysql/__init__.py", line 88, in Connect
return Connection(*args, **kwargs)
File "/home/loctv/Documents/Python/WebCrawling/scarpingEnv/local/lib/python2.7/site-packages/PyMySQL-0.6.2-py2.7.egg/pymysql/connections.py", line 626, in __init__
self._connect()
File "/home/loctv/Documents/Python/WebCrawling/scarpingEnv/local/lib/python2.7/site-packages/PyMySQL-0.6.2-py2.7.egg/pymysql/connections.py", line 818, in _connect
2003, "Can't connect to MySQL server on %r (%s)" % (self.host, e))
pymysql.err.OperationalError: (2003, "Can't connect to MySQL server on '127.0.0.1' ([Errno 2] No such file or directory)")


Here’s my way to fix this shit:
I figured out that the reason is not because MySQL server cannot connect on ‘127.0.0.1’, the reason is the socket name, which is ‘/tmp/mysql.sock’ is wrong.
To fix this, type this command in terminal

mysqladmin -u root -p variables | grep socket


This is what I get: As you can see, the socket name is not ‘/tml/mysql.sock’, it is ‘/var/run/mysqld/mysqld.sock’
So I copy that name, and change the script into:

import pymysql
# connect with mysql
conn = pymysql.connect(host='127.0.0.1', unix_socket='/var/run/mysqld/mysqld.sock',
user='root', passwd='02390128', db='mysql')
cur = conn.cursor()
cur.execute("USE scraping;")
cur.execute("SELECT * FROM pages WHERE id=1")
print(cur.fetchone())
cur.close()
conn.close()


Notice that this is one of the many solutions to fix this, it’s just that this works for me. So if you get into the same issue, and still not be able to fix it, let’s try this out.

• ## Fix: ImportError: cannot import name PDFDocument (when using slate)

I  spent over an hour to fix this problem. I write this post to avoid searching again and share the solution I used. Up to this point, this solution still works perfectly, I don’t know if it still work in the future, since the owner of slate package said he’s gonna change the code.

After installing slate, and you type in

import slate


and you get this error

Traceback (most recent call last):
File "<console>", line 1, in <module>
File "/usr/local/lib/python2.7/dist-packages/slate/__init__.py", line 48, in <module>
from slate import PDF
File "/usr/local/lib/python2.7/dist-packages/slate/slate.py", line 3, in <module>
from pdfminer.pdfparser import PDFParser, PDFDocument
ImportError: cannot import name PDFDocument


In this post, there are many ways to solve this problem, but not all of them can be applied. And I found the solution from rdpickard .  It’s not quite elegant, but it fixes shit.

If you’re afraid of clicking the link above, here’s what he wrote:

Not sure if editing the slate.py is an option for people’s environment, but if you change

line 3

from pdfminer.pdfparser import PDFParser, PDFDocument


to

from pdfminer.pdfparser import PDFParser
from pdfminer.pdfdocument import PDFDocument
from pdfminer.pdfpage import PDFPage


line 38

        self.doc = PDFDocument()


to

        self.doc = PDFDocument(self.parser)


comment out lines 40 & 41

line 49

            for page in self.doc.get_pages():
self.append(self.interpreter.process_page(page))


to

            for page in PDFPage.create_pages(self.doc):
self.append(self.interpreter.process_page(page))


it works.

Here are the versions of libraries I am using

cssselect==0.9.1
lxml==3.6.0
pdfminer==20140328
pyquery==1.2.13
slate==0.3
wheel==0.24.0


That’s it.

If you cant change the code inside slate.py, it probably means you don’t have permission. If you’re using Linux, type this line into terminal

sudo chown yourusername:yourusername path_to_file_or_folder_you_want_to_get_permission


• #### Gulsah Ayhan 11:36 pm on November 8, 2017 Permalink | Reply

Thanks for the solution, however I still have the same error • ## Simple Python script for unzipping

import sys
import zip file

def unzip(zipfile_path, tofolder_path):
zip_ref = zipfile.ZipFile(zipfile_path, 'r')
zip_ref.extractall(tofolder_path)
zip_ref.close()

def main():
if len(sys.argv) != 3:
raise Exception('Must be 3 arguments')
else:
zipfile_path, tofolder_path = sys.argv[1:]
unzip(zipfile_path, tofolder_path)

if __name__ == '__main__':
main()


Github:

• ## DynamicArray in Python

Using ctypes module, we can create a new DynamicArray type. See more ctypes documentation to understand.

import ctypes

class DynamicArray:
def __init__(self):
""" Create an empty array """
self._n = 0 # count actual elements in array
self._capacity = 1
self._A = self._make_array(self._capacity)

def __len__(self):
""" Return number of elements stored in array """
return self._n

def __getitem__(self, k):
""" return element at index k """
if not 0 <= k < len(self):
raise IndexError('invalid index')
return self._A[k] # retrieve from array

def append(self, obj):
""" Add object to the end of array """
if len(self) == self._capacity: # not enough room
self._resize(2 * self._capacity) # so double capacity
self._A[self._n] = obj
self._n += 1

def _resize(self, c):
""" Resize the old array to capacity c """
print 'Call resize'
B = self._make_array(c) # new bigger array
for k in xrange(self._n): # copy the old array to bigger array
B[k] = self._A[k]
self._A = B
self._capacity = c

def _make_array(self, c):
""" Return a new array with capacity c """
return (c * ctypes.py_object)() # see ctypes documentation

def insert(self, k, value):
""" Insert value at index k in array by shifting rightmost elements to the right """
if not 0 <= k < len(self):
raise IndexError('invalid index')
if self._n == len(self): # not enough room
self.resize(2 * self._capacity) # double capacity
for j in range(self._n, k, -1): # shift rightmost first
self._A[j] = self._A[j-1]
self._A[k] = value # get new element
self._n += 1

def remove(self, value):
""" remove the first occurence of value """
for k in xrange(len(self)):
if self._A[k] == value: # found
for j in range(k, len(self)-1): # shift all elements on the right side to left
self._A[j] = self._A[j+1]
self._A[len(self)-1] = None # garbage collection
self._n -= 1 # reduce n
return # exit immediately

def __str__(self):
""" presentation of dynamic array (user friendly form) """
pre = "["
for i in xrange(len(self)):
pre += str(self[i]) + (", " if i < len(self)-1 else "]")
return pre

# test out the DynamicArray
if __name__ == '__main__':
arr = DynamicArray()
for i in range(100):
arr.append(i)
# print call resize 7 times
print arr


An attribute (instance, method) with zero underscore is considered as public. One underscore is protected and two is private. Try it yourself, if you use two underscore, you cannot access the object’s attributes outside of class.

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r