LeetCode Blog for course "Algorithms" -- Problem 11

Problem 11. Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.


My solution in Python:

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left, right = 0, len(height) - 1
        ans = 0
        while left < right:
            if height[left] < height[right]:
                area = height[left] * (right - left)
                left += 1
            else:
                area = height[right] * (right - left)
                right -= 1
            ans = max(ans, area) 
        return ans

Review:

This problem belongs to the more simple ones. The trick here is that we don't really need to examine all combinations of two vertical lines, we only need to discard the shorter one. The height used in calculating area is the shorter one of the two lines, so it does no good to retain the shorter one after computing the current area. We move on and retain the longer line, until the two lines meet.

LeetCode Blog for course "Algorithms" -- Problem 9

Problem 9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

My solution in Python:

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
        copy, reverse = x, 0

        while copy:
            reverse *= 10
            reverse += copy % 10
            copy /= 10

        return x == reverse

Review:

After much thought, I cannot solve the problem without using extra space, so my solution does use some extra space as a new integer is constructed.
Negative numbers cannot be palindromic due to the preceding "-" sign which doesn't exist at the end, so we first check whether the given number is less than 0.
If it is greater than or equals 0, we construct a reversed version of this integer, then compare them. If the original integer equals to its reversed version, then the number is palindromic.

LeetCode Blog for course "Algorithms" -- Problem 8

Problem 8. String to Integer (atoi)

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (i.e. no given input specs). You are responsible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

My solution in Python:

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.strip()
        if str == "" :
            return 0
        i = 0
        sign = 1
        ret = 0
        length = len(str)
        MaxInt = (1 << 31) - 1
        if str[i] == '+':
            i += 1
        elif str[i] == '-' :
            i += 1
            sign = -1
        
        for i in range(i, length) :
            if str[i] < '0' or str[i] > '9' :
                break
            ret = ret * 10 + int(str[i])
            if ret > sys.maxint:
                break
        ret *= sign
        if ret >= MaxInt:
            return MaxInt
        if ret < MaxInt * -1 :
            return MaxInt * - 1 - 1 
        return ret

Review:

According to the requirements in the description, as long as the string starts with number digits (ignoring whitespaces), that substring of number digits is converted to an integer. So first we use the "strip" function to remove all consecutive whitespaces from the beginning and end of the original string. Then we check if there is a sign character ("+" or "-") at the start of the string. Then we read the string one character by one character until a non-number character or the end of the string is reached. We check if the converted integer exceeds the limits of integer. The algorithm ends here.

LeetCode Blog for course "Algorithms" -- Problem 7

Problem 7. Reverse Integer

Reverse digits of an integer.
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? i.e. cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

My solution in Python:

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return 0
            
        neg = 1
        if x < 0:
            neg, x = -1, -x
        
        reverse = 0
        while x > 0:
            reverse = reverse * 10 + x % 10
            x = x / 10
        
        reverse = reverse * neg
        if reverse < -(1 << 31) or reverse > (1 << 31) - 1:
            return 0
        return reverse

Review:

This problem belongs to the more simple questions. However, we do need to consider the special conditions, such as numbers that exceeds the limit of 32 bits when reversed. Therefore, after reversing all the digits, we check to see whether it exceeds -(1<<31) or (1>>31), and if it does, we set the reversed value to 0.

LeetCode Blog for course "Algorithms" -- Problem 6

Problem 6. Zigzag Conversion

Write the code that will take a string and make this conversion given a number of rows.

My solution in Python:

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows==1: return s
        tmp=['' for i in range(numRows)]
        index=-1; step=1
        for i in range(len(s)):
            index+=step
            if index==numRows:
                index-=2; step=-1
            elif index==-1:
                index=1; step=1
            tmp[index]+=s[i]
        return ''.join(tmp)

Review:

This problem asks us to convert a given string to a zigzag form, giving the number of rows the zigzag shape should contain of. It does not require the exact shape to be drawn, only the result string combining the rows of the zigzag is required. Thus, this problem is basically asks for a new arrangement of the original string.
First we construct a certain number of strings, the number of strings equals to the number of rows in the zigzag. Then for each character in the original string, we decide which of the substrings should it goes to (be appended to). The decision is made using the following procedure.
First we put the first character in the original string in the first substring. Then for each following letter, we put it in the next substring (the next row in the zigzag). This is achieved by setting the "step" variable (increment) to 1.
When the last row of the zigzag is reached, after putting the corresponding letter in that row, we alter the value of "step" to -1. Thus in each following iteration, rather than going down, we going up along the zigzag, putting the next letter one row above the previous one. "Step" is again set to 1 when the first row of the zigzag is reached.
The algorithm ends when the last letter in the original string is processed this way.

LeetCode Blog for course "Algorithms" -- Problem 3 & 5

Problem 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.


My solution in Python:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ answer = 0; left = 0; last = {}; for i in range(len(s)): if s[i] in last and last[s[i]] >= left: left = last[s[i]] +1; last[s[i]] = i; answer = max(answer, i - left + 1); return answer;

Review:
We make good use of the "dictionary" in Python here. Starting with the first character in the string, we go through the string characters one by one, and store one item in the dictionary, with the character being the key, and the place it appears in the string being the value. When we encounter a character that has already appeared previously, we immediately know because this particular key (the character) is already in the dictionary. Thus we move the starting character of the substring to the next position of which the repeated character first appeared in the original string. We then compare the length of the current non-repeated-character-substring with the longest substring we already know. When "i" reaches the last character of the original string, the "answer" should be the length of the longest substring without repeated character.


Problem 5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:
Input: "cbbd"
Output: "bb"

My solution in Python: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ ansl, ansr, maxx = 0, 0, 0 length = len(s) for i in range(1, length * 2): if i & 1 : left = i / 2 right = left else : left = i / 2 - 1 right = left + 1 while (left >= 0) and (right < length) and (s[left] == s[right]): left -= 1 right += 1 left += 1 right -= 1 if right - left > maxx: maxx = right - left ansl = left ansr = right return s[ansl: ansr + 1]

Review:
We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only $\mathrm{2n-1}$ such centers. By treating odd "i" and even "i" differently, we are able to examine both palindromes with even length and with odd length. This question is actually very interesting and has many (at least 5) different solutions, each with different time and space efficiency. The most advanced one, the Manacher's algorithm, can be found here.

LeetCode Blog for course "Algorithms" -- Problem 1 & 2

Problem 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My solution in Python:

1 2 3 4 5 6 7 8 9 10

class Solution(object):     def twoSum(self,nums,target):         first=0         second=0         for x in range(0,len(nums)):             for y in range(x+1,len(nums)):                 if nums[x]+nums[y]==target:                     first=x                     second=y                     return [first,second]

Review:
We use nested iterations here. For each number in the array, we go through the numbers in the array after it to see if there is a required match. Because there is only one such pair that suits the requirement (add up to a specific target), once we find such a match, we can stop the iteration here.


Problem 2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

My solution in Python:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ answer = ListNode(0); pointer = answer; carry = 0; while True: if l1 != None: carry += l1.val; l1 = l1.next; if l2 != None: carry += l2.val; l2 = l2.next; pointer.val = carry % 10; carry /= 10; if l1 != None or l2 != None or carry != 0: pointer.next = ListNode(0); pointer = pointer.next; else: break; return answer;

Review:
Given that the digits are stored in reverse order in the list, the first node in the list is the least significant bit in the integer, so we can add the two lists directly from the first node to the last node. The solution is very straight-forward. Note that along with checking whether both l1 and l2 have reached their ends, we also must check whether the carry bit equals 0. A non-zero carry bit must be carried to the next iteration and have a new node in the answer list to store it. When both l1 and l2 have reached their end, and the carry bit is 0, the algorithm ends.

2017年8月12日 在以色列海法

今天一整天宅在宿舍. 基本没干啥.

晚上出去到ATM上取了700块钱.

今天没写作业.

明天去耶路撒冷. 要早起. 明早五点钟就要在宿舍楼下集合.

安息日的学校. 基本上是空无一人.

2017年8月11日 在以色列海法

今天在宿舍宅了一整天.

本来是说打算今天把第二次作业写完然后后面周二(15号, 第二次作业due date)就不用着急回来的, 可惜现在晚上十点了, 作业还一笔没动, 唉. 要不一会儿写完日记开始写作业吧.

今天上午订了旅店, 在耶路撒冷. 本来打算订Panorama Hotel来着, 但是女生们说她们订的是另一个, 在耶路撒冷Old City的一个Hostel, 条件差一点但是也还可以, 我就也订了这一个. 只订了一天(周日晚).

上午订了旅店, 在booking.com.

中午做饭. 辣椒炒鸡蛋. 煮了一些大米饭, 煮得有点多, 还好, 但问题是水加得还是有点多了, 昨天煮饭水加得就实在太多, 今天是稍稍有些多. 不知道是电饭锅的问题, 还是以色列大米的问题, 还是水的问题, 还是各种不良因素综合起来导致, 总之煮出来的大米饭非常松懈, 完全不像东北大米那样有口感. 可以说这里的大米煮出来基本和广东的大米一样难吃了, 或许更差一点? 辣椒炒鸡蛋还不错, 唯一的不足是量有点少. 一个大辣椒加上两个鸡蛋, 感觉炒完了我一个人吃都不怎么够额.

宿舍里只有我和另一个清华的本科的同学, 其他人都出去旅游去了.

下午好像啥也没干. 嗯, 确实啥也没干.

晚上做饭. 煮面条, 三块面饼, 一个西红柿, 切了几刀以后一起煮. 捞出来加上番茄酱. 番茄酱加得实在太多, 真的不怎么好吃. 晚饭不太满意, 当然还是比刚来以色列的时候整天对付的那些东西好了太多, 当时每天吃的就是汉堡加随便什么面包啊小点心啊什么的, 吃多了真是受不了.

晚上研究了很长时间该用什么东西写日记. 其实最开始一直是打算用豆瓣的, 毕竟之前(去年)用过很短的一段时间, 感觉起来还不错. 但问题是最近的照片特别多, 每次备份到Google Photos以后我都会把手机里的照片文件删掉, 偏偏用豆瓣写日记, 要插入照片只能插入本地文件, 这就导致非常麻烦. 我试了一下从Google Photos把照片下载下来再插入, 实在太麻烦, 只能放弃.

然后考虑了使用日记本手写. 又有了买好日记本的冲动. 不过这个办法缺点实在太多, 不方便携带, 容易丢, 写得慢, 没法加照片, 等等. 优点就是情怀加上用各种笔各种颜色感觉起来很好玩. 但说实话缺点实在太过严重, 远远盖过有点, 只能作罢了.

后来就发现Blogger居然支持直接加入Google Photos的照片, 这个很意外, 直接就导致我非常喜欢Blogger了, 所以现在正在用它写日记.

刷知乎看到了一个"吾志", 怎么说呢, 优点非常明显, 就是功能特别简洁, 界面干净, 日记写完了不能修改(这点我真的很喜欢), 以及界面和功能真的很干净(对我很重要). 缺点就是, 功能有点太过于简陋了, 只能文字, 而且只有正文, 连标题都没有, 还有一个问题就是, 它毕竟是一个比较小的网站, 虽然用了https加密, 但说真的在服务器端还是能看到我写的全部内容的, 这就... 让我感觉不是很放心. 当然是我想的比较多了, 但还是确实不太放心.

所以就选择Blogger啦! 目前是把可见性设置为了只有自己可见, 日后需要调整的时候再说吧.

试一下加入几张照片看看.

今天炒的辣椒. 还没加鸡蛋.

昨天晚上的辣椒炒鸡蛋. 黄色的方块是车达奶酪.

埃拉特两日游

8月8号和9号去了埃拉特.

8号一大早上三点多就起床了, 慢慢悠悠地吃了两杯冷牛奶泡麦片(其实是某种谷物做的小球), 喝了一杯咖啡, 刷牙洗澡等等... 五点多钟出门去.

约好六点钟在楼下的公交车站集合. 虽然时间很早, 但由于起床已经两个多小时, 其实并没有感觉很困.

算了, 有点想不起来之前发生了什么, 也不太愿意去想. 我还是每天写当天的日记就好了! 哈哈, 放弃. 一会儿写写今天都干了些啥.

Canny Edge Detector Implementation using CImg

This time, we are going to implement the famous Canny edge detector, which is probably the most used edge detector in the field of computer vision.

This implementation is pretty well encapsulated, and it, as many other algorithm implementations in this Blog, is quite straight forward and really easy to understand, thus should not cause any problem in comprehension as long as you know the very basics of the Canny operator.

The canny.h header is as follows.

#pragma once

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include "canny.h"
#include "CImg.h"

using namespace std;
using namespace cimg_library;

class canny
{
public:
    canny::canny(string fileName);

    CImg<float> outS, outG, outO, outT, outNMS;

    void canny::CannyDiscrete(CImg<float> in, float sigma, float threshold,
        CImg<float> &outSmooth, CImg<float> &outGradient,
        CImg<float> &outOrientation, CImg<float> &outThreshold,
        CImg<float> &outNMS);
};

The canny.cpp source file is as follows.

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include "canny.h"
#include "CImg.h"
#include "gauss_filter.h"
#include "non_maximum_suppression.h"

using namespace std;
using namespace cimg_library;

canny::canny(string fileName)
{
    // image after non-max-suppression
    string infile = "Input.bmp";      // required input filename
    string outfileNMS = "Output.bmp";       // saving the binary canny edges to file?

                                                 // canny parameters
    float sigma = 1.5f;
    float threshold = 1.0f;

    cout << endl << endl << "sigma = " 
         << sigma 
         << endl << "threshold = " 
         << threshold << endl << endl;

    //***** read image *****************//
    CImg<float> inColor(infile.c_str());
    CImg<float> in = inColor; // ensure greyscale img!
    const int widthIn = in._width;
    const int heightIn = in._height;

    //***** apply Canny filter *********//
    CannyDiscrete(in, sigma, threshold, outS, outG, outO, outT, outNMS);

    //***** display output images ******//
    outNMS.display("non-maximum suppression");


    //***** write output images ********//
    if (outfileNMS.length()>0) {
        std::cout << endl << endl 
                  << "saving gradient to " << outfileNMS 
                  << std::endl << endl;
        outNMS.save(outfileNMS.c_str());
    }

}

void canny::CannyDiscrete(CImg<float> in, 
float sigma, float threshold,CImg<float>& outSmooth, 
                             CImg<float>& outGradient,
                             CImg<float>& outOrientation, 
                             CImg<float>& outThreshold, 
                             CImg<float>& outNMS)
{
    const int nx = in._width;
    const int ny = in._height;

    /************ initialize memory ************/
    outGradient = in; outGradient.fill(0.0f);
    CImg<int> dirmax(outGradient);
    CImg<float> derivative[4];
    for (int i = 0; i < 4; i++) { derivative[i] = outGradient; }
    outOrientation = outGradient;
    outThreshold = outGradient;
    outNMS = outGradient;

    /************** smoothing the input image ******************/
    CImg<float> filter;
    gauss_filter(filter, sigma, 0);
    outSmooth = in.get_convolve(filter).convolve(filter.get_transpose());


    /************ loop over all pixels in the interior **********************/
    float fct = 1.0 / (2.0*sqrt(2.0f));
    for (int y = 1; y < ny - 1; y++) {
        for (int x = 1; x < nx - 1; x++) {
            //***** compute directional derivatives (E,NE,N,SE) ****//
            float grad_E = (outSmooth(x + 1, y) - outSmooth(x - 1, y))*0.5; // E
            float grad_NE = (outSmooth(x + 1, y - 1) - outSmooth(x - 1, y + 1))*fct; // NE
            float grad_N = (outSmooth(x, y - 1) - outSmooth(x, y + 1))*0.5; // N
            float grad_SE = (outSmooth(x + 1, y + 1) - outSmooth(x - 1, y - 1))*fct; // SE

            //***** compute gradient magnitude *********//
            float grad_mag = grad_E*grad_E + grad_N*grad_N;
            outGradient(x, y) = grad_mag;

            //***** compute gradient orientation (continuous version)*******//
            float angle = 0.0f;
            if (grad_mag > 0.0f) { angle = atan2(grad_N, grad_E); }
            if (angle < 0.0) angle += cimg::PI;
            outOrientation(x, y) = angle*255.0 / cimg::PI + 0.5; // -> outOrientation

            //***** compute absolute derivations *******//
            derivative[0](x, y) = grad_E = fabs(grad_E);
            derivative[1](x, y) = grad_NE = fabs(grad_NE);
            derivative[2](x, y) = grad_N = fabs(grad_N);
            derivative[3](x, y) = grad_SE = fabs(grad_SE);

            //***** compute direction of max derivative //
            if ((grad_E>grad_NE) && (grad_E>grad_N) && (grad_E>grad_SE)) {
                dirmax(x, y) = 0; // E
            }
            else if ((grad_NE>grad_N) && (grad_NE>grad_SE)) {
                dirmax(x, y) = 1; // NE
            }
            else if (grad_N>grad_SE) {
                dirmax(x, y) = 2; // N
            }
            else {
                dirmax(x, y) = 3; // SE
            }
            // one may compute the contiuous dominant direction computation...
            //outOrientation(x,y) = dirmax(x,y)*255.f/4;  
        }
    } // for x,y

      // directing vectors (E, NE, N, SE)
    int dir_vector[4][2] = { { 1,0 },{ 1,-1 },{ 0,-1 },{ 1,1 } };
    // direction of max derivative of
    // current pixel and its two neighbouring pixel (in direction of dir)
    int dir, dir1, dir2;

    //***** thresholding and (canny) non-max-supression *//
    for (int y = 2; y < ny - 2; y++) {
        for (int x = 2; x < nx - 2; x++) {
            dir = dirmax(x, y);
            if (derivative[dir](x, y) < threshold) {
                outThreshold(x, y) = 0.0f;
                outNMS(x, y) = 0.0f;
            }
            else {
                outThreshold(x, y) = 255.0f;
                int dx = dir_vector[dir][0];
                int dy = dir_vector[dir][1];
                dir1 = dirmax(x + dx, y + dy);
                dir2 = dirmax(x - dx, y - dy);
                outNMS(x, y) = 255.f*
                    ((derivative[dir](x, y) > derivative[dir1](x + dx, y + dy)) &&
                    (derivative[dir](x, y) >= derivative[dir2](x - dx, y - dy)));
            } // -> outThreshold, outNMS
        }
    } // for x, y...
}

The gauss_filter.h header is as follow.

#include "CImg.h"
using namespace cimg_library;


/** compute Gaussian derivatives filter weights
* \param sigma = bandwidth of the Gaussian 
* \param deriv = computing the 'deriv'-th derivatives of a Gaussian
* the width of the filter is automatically determined from sigma.
* g  = \frac{1}{\sqrt{2\pi}\sigma}   \exp(-0.5 \frac{x^2}{\sigma^2} )
* g' = \frac{x}{\sqrt{2\pi}\sigma^3} \exp(-0.5 \frac{x^2}{\sigma^2} )
*    = -\frac{x}{\sigma^2} g
* g''= (\frac{x^2}{\sigma^2} - 1) \frac{1}{\sigma^2} g
*/
void gauss_filter (CImg<float>& filter, float sigma=1.0f, int deriv=0) {
    float width = 3*sigma;               // may be less width?
    float sigma2 = sigma*sigma;
    filter.assign(int(2*width)+1);

    int i=0;
    for (float x=-width; x<=width; x+=1.0f) {
        float g = exp(-0.5*x*x/sigma2) / sqrt(2*cimg::PI) / sigma;
        if (deriv==1) g *= -x/sigma2;
        if (deriv==2) g *= (x*x/sigma2 - 1.0f)/sigma2;
        filter[i] = g ;
        //printf ("i=%f -> %f\n", x, filter[i]);
        i++;
    }
}

The non_maximum_suppression.h header is as follow.

#ifndef NON_MAXIMUM_SUPPRESSION_H
#define NON_MAXIMUM_SUPPRESSION_H

#include <vector>
#include "CImg.h"
using namespace cimg_library;
using namespace std;

/** a vector of pixel coordinates.
* Usage:
*    unsigned i;
*    int x, y;
*    TVectorOfPairs nonmax;
*    nonmax.push_back (make_pair(x,y));   // adding new pixel coordinates:
*    x = nonmax[i].first;                 // get x-coordinate of i-th pixel
*    y = nonmax[i].second;                // get y-coordinate of i-th pixel
*/
typedef std::vector<std::pair<int,int> > TVectorOfPairs;

/** apply non-maximum suppression
* \param input: some float image
* \param nonmax: a list of (x,y)-tuple of maxima
* \param thresh: ignore those with too small response
* \param halfwidth: halfwidth of the neighbourhood size
*/
void non_maximum_suppression (CImg<float>& img, TVectorOfPairs& nonmax,
                              float thresh, int halfwidth) 
{
    nonmax.clear();
    for (int y=halfwidth; y<img._height-halfwidth; y++) {
        for (int x=halfwidth; x<img._width-halfwidth; x++) {
            float value = img(x,y);
            if (value<thresh) { continue; }

            bool ismax = true;
            for (int ny=y-halfwidth; ny<=y+halfwidth; ny++) {
                for (int nx=x-halfwidth; nx<=x+halfwidth; nx++) {
                    ismax = ismax && (img(nx,ny)<=value);
                }}
            if (!ismax) continue;

            nonmax.push_back (make_pair(x,y));
        }}
}

#endif /* NON_MAXIMUM_SUPPRESSION_H */

The testing Main.cpp is as follow.

#include <iostream>
#include <string>
#include <vector>
#include "canny.h"
#include "CImg.h"

using namespace std;
using namespace cimg_library;

int main()
{
    string filePath = "Input.bmp";
    canny test(filePath);

    system("pause");
    return 0;
}

Just copy all these files into your Visual Studio 2017 solution, and hopefully it should work correctly. Hope you like this.

Draw Some Basic Shapes Using OpenGL

Here, we are required to draw some basic shapes (squares, triangles, etc.) using OpenGL.

We use the so-called "old-fashioned" OpenGL.

Below is the code.

#include <GL/glew.h>
#include <GLFW/glfw3.h>
#include <iostream>
#include <GL/gl.h>
#include <GL/glut.h>

using namespace std;


void renderScene(void)
{
    glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

    // Draw a green triangle.
    glBegin(GL_TRIANGLES);
    glColor3f(0.0f, 1.0f, 0.0f);
    glVertex3f(0.3, 0.3, 0.0);
    glVertex3f(0.4, 0.4, 0.0);
    glVertex3f(0.4, 0.6, 0.0);
    glEnd();

    // Different colors for each vertex.
    glBegin(GL_TRIANGLES);
    glColor3f(1.0f, 0.0f, 0.0f);
    glVertex3f(0.0, 0.1, 0.0);
    glColor3f(0.0f, 1.0f, 0.0f);
    glVertex3f(0.1, -0.1, 0.0);
    glColor3f(0.0f, 0.0f, 1.0f);
    glVertex3f(-0.1, -0.1, 0.0);
    glEnd();
    
    // Draw a line.
    glBegin(GL_LINE_STRIP);
    glColor3f(1.0f, 0.0f, 0.0f);
    glVertex2f(0.5, 0.5);
    glVertex2f(0.7, 0.7);
    glEnd();

    // Draw a polygon.
    glBegin(GL_POLYGON);
    glVertex2f(0.75, 0.75);
    glVertex2f(0.75, 0.95);
    glVertex2f(0.95, 0.95);
    glVertex2f(0.95, 0.75);
    glEnd();

    // Draw a triangle strip.
    glBegin(GL_TRIANGLE_STRIP);
    glVertex2f(-0.3, -0.3);
    glVertex2f(-0.3, -0.5);
    glVertex2f(-0.6, -0.7);
    glVertex2f(-0.6, -0.4);
    glVertex2f(-0.9, -0.9);
    glEnd();
    
    glFlush();
}

int main(int argc, char *argv[])
{
    glutInit(&argc, argv);
    glutCreateWindow("Hello OpenGL");
    glutDisplayFunc(renderScene);
    glutMainLoop();
    return 0;

}

This is by far the simplest implementation of drawing a triangle using OpenGL I have seen on the Internet. I'm sure you are going to appreciate this, because it's really simple.

Very Basic Image Manipulations with CImg

First, we use the image called "1.bmp" as input.

We change the white area into color red, and the black area into color green.

Then we draw a circle on the image, with its center at (50,50), its radius 30, its color blue.

Next we draw another circle on the image, with its center at (50,50), its radius 3, its color yellow.

Finally, display the modified image with the image.display() function.

Blow is the code.

#include<iostream>
#include"CImg.h"

using namespace std;
using namespace cimg_library;

int main()
{
    CImg<unsigned char> image("1.bmp");
    for (int row = 0;row < image.height();row++)
    {
        for (int column = 0;column < image.width();column++)
        {
            if (image(row, column, 0, 0) == 255)
            {
                image(row, column, 0, 1) = 0;
                image(row, column, 0, 2) = 0;
            }
            else if (image(row, column, 0, 0) == 0)
            {
                image(row, column, 0, 0) = 0;
                image(row, column, 0, 1) = 255;
                image(row, column, 0, 2) = 0;
            }
            else;
        }
    }
    float blue[] = { 0.0f,0.0f,255.0f };
    int yellow[] = { 255,255,0 };
    image.draw_circle(50, 50, 30, blue, 1);
    image.draw_circle(50, 50, 3, yellow, 1);
    image.display();
    system("pause");
    return 0;
}

The Very First Try

This is my very first essay on Blogger.