Ben's Heaven

  相信各位做影像的同行在驗證自己演算法的時候， 總是像我一樣眼見為憑、需要把圖片秀出來對吧？

本篇文章來自  想知道網戀對象有沒有修圖嗎？試試看這款修圖偵測機器人！  的續篇， 因為 Python 的方法實在是太慢了，所以我一直在尋求加速的方法。 俗話說得好： 要看一個人怎麼做立委， 就要看他怎麼做立委！ 不是，我是說有些人可能不適合做立委、適合做總統！ 舉個例子： 拿 Python 去做文字處理就很開心，但是拿 C/CPP 去做文字處理你就準備腦血栓； 反之拿 Python 做數學運算也會慢到中風，但是拿 C/CPP 做數學運算就風馳電掣。 所以我用 CPP 實現了需要數學運算的 DCT 方法， 主要是使用 extern "C" 方法來與 Python 對接，在 Python 那邊設定好輸出入的參數。 這邊比較需要注意的是因為我選用的讀圖方式是 OpenCV 的 CPP 函式庫， 所以寫 Makefile 的時候需要注意把 OpenCV 包進來。 在編譯的過程中 Makefile 也會發生抓不到 g++ 的時候 （想好好編譯真難 😇） 總之做了一點 Soft-link 還有 Dirty work 後終於能正確編譯了。 因為我是用"Single Thread"、"Mask" 的方法來實現 DCT 變換的， 所以讓我們來看看與 Python 版 與 CPP 版 比較效果如何： CPP 版的運算速度比 Python 版快了近六倍， 有夠優質！ 相關開源我更新在： https://github.com/wuyiulin/GraphAppBot 想要測試一下這個服務： https://t.me/DynamicGraphApp_bot 如果有任何問題歡迎聯絡我： wuyiulin@gmail.com

  這邊提供 OpenCV 編譯後崩潰的可能解決方法： 我的環境是 OpenCV 4.5.4、Ubuntu 22.04， 並使用 g++ 11.4.0 編譯我的專案。 我遇到的情境問題是，我得到一包 C/C++ 的專案， 裡面用 Makefile 來整合編譯專案，裡面包含我自己寫的一段高斯濾波程式碼。 這貨整包編譯時沒有出錯； 獨立把高斯濾波程式碼放到另一個編譯、運行也都沒有出錯。 但當我在源碼裡面運行這段高斯濾波程式碼時"有機率"會出錯： int ksize = 3; cv::Size size = image.size(); int width = size.width; int height = size.height; cv::Mat blurred_image(height, width, CV_8UC1, cv::Scalar::all(0)); cv::GaussianBlur(grey, blurred_image, cv::Size(ksize, ksize), 0, 0); 然而我給定的高斯核大小為 3x3， 非常奇怪，程式會跳說高斯核定義不是奇數，所以不合法： error: (-215:Assertion failed) ksize.width > 0 && ksize.width % 2 == 1 && ksize.height > 0 && ksize.height % 2 == 1 in function 'createGaussianKernels' 除此之外，當我想使用旋轉圖片、在圖片上畫點的功能也全部失效，但是編譯又沒有出錯， 這件事情真的是非常奇怪。 因為是運行時錯誤，於是我先用 GDB 檢查了函式是否重複定義： 然而並沒有，這就奇了怪了。 後來我開始埋 log 想辦法抓鬼，也完全抓不到。 解決方法： 把專案的 Makefile 打開，有關於 OpenCV 的部份改寫， 讓  Makefile 繞過 pkg-config ，手動給定 OpenCV.hpp 還有 libopencv_XXX.so 的路徑。 如果我的  OpenCV.hpp 放在  /usr/inclu...

  這篇主要介紹 Linux/Windows 兩個平臺使用 Intel 內顯資源開發 OpenCL 的解決方案， 並且不用重新編譯核心，不像 這篇 太 Hardcore 了xD

2023 - 11 瑞鼎 - 觸控演算法工程師 工作內容 1. 客戶需求專案支援 2. 觸控演算法開發與維護 3. 觸控演算法數據分析 職務類別 演算法工程師 白板題

繼  200. Number of Islands  後，又遇到一個影像處理的問題。 這題要用動態規劃來解，菜雞如我第一時間沒想到動態規劃， 但是後來也自己解出來了，紀錄一下我的解題心路歷程。 題目簡介： 給你一張尺寸為 m x n 像素且只包含（0,1）的圖片稱為 Matrix ， 其中 1 代表有像素的區域，找出此張圖片中含有 1 的最大正方形區域面積。 第一階段想法：循序檢測法 把每個點都當作候選正方形的左上角， 先求 Row 再驗證每個 Col 是否符合正方形區域預想？ 若有，就回傳正方形區域面積； 若無，就回傳 0。 假設圖片中有 N 個元素，這個想法的時間複雜度為： $$O(N^{2})$$ 但是我們會遇到一個特殊情況，當最大正方形在驗證失敗的候選正方形的的情況， 像是： 就很尷尬，其中 $$S_m$$ 不等於 6 的原因是本圖中最大正方形是交由 min(m, n) 決定， 所以不用檢查到 $$S_m = 6$$ 可以降低計算時間。 結果： Wrong Answer 第二階段：動態規劃法 所以我決定再不增加時間複雜度的情形下，由小到大、每個正方形都檢測。 使用動態規劃，每一步驟又拆成兩小步： 第一步：驗證對角線是否為 '1' ？ 第二步：驗證相應 X, Y軸是否為 '1' ？ 若有任一步檢測到 '0' ，則回傳步數 S 的平方當作正方形面積。 不過鑑於這個作法時間複雜度遇到 Worst Case （全為 '1' 的圖片時）仍為 $$O(N^{2})$$ 結果： Time Limited Error 第三階段：利用影像（數據）特性降低時間複雜度。 問自己一個問題： 最低滿足圖片中最大正方形的條件是什麼？ 答案是任何大於（長/2）*（寬/2）的正方形， 因為本題目中不考慮重疊問題，所以用數學上來說： 一圖片尺寸為 m*n ，若有任意正方形面積大於（m/2 + k）（n/2 + k）， 而 k 恆大於零的話，此正方形為圖片中最大的正方形就成立。 而候選次大正方形面積必定為（m/2 - k）（n/2 - k）， 所以每個點出發後， 檢測 (m*n/4) + m + n - 1 個像素就知道這個正方形是不是最大的了。 結果： Accept

因為最近在解 Leetcode 的  91.   Decode Ways ， 要用到 Fibonacci  sequence  來解，就我所知上次解  70 .  Climbing Stairs  的時候， 用 recursive 求解   Fibonacci   sequence 的時候會 TLE。 （所以我就偷懶跑去用 Python3 解大數） 這次再遇到應該是要進步了xDDD 正文開始： Fibonacci  sequence 會長這個樣子： 根據基本定義，第 N 個  Fibonacci value 等於前兩個  Fibonacci value 相加， 我們便可以得到公式： 得到公式以後把它擴展成 轉移矩陣 M 的形式， 因為我們把前兩項當作初始值，所以 轉移矩陣 M 的指數會減二： 所以我們現在只要計算 M 的 (n-2) 次方就能得到第 N 個  Fibonacci value。 （左上角的 M00 會等於 第N個  Fibonacci value ） 此時的計算複雜度為： O(n) 以第 45 個 value 值來比較，此方法已經比遞迴快很多了xD 但是我還要教你一個威力加強版外掛：平方求冪 （左岸又稱快速冪 or  double-and-add ） 我們在這裡要用平方求冪去優化轉移矩陣 M。 平方求冪的想法是把任何高階指數都化為與指數二有關的指數和， 屁話一堆直接看數學比較快： 如果你說 n 是 odd 怎麼辦？ 啊不簡單？直接減一再乘回去R~： 這樣的好處是能大大的減少計算量，數學意義上來說是二分搜尋法， 以找 n = 16 舉例， 沒有平方求冪的版本會很老實地計算十五次乘法， 而有平方求冪外掛的版本會跳著算： 像是圖中有幾個節點，就計算幾次， 每次都是跟自己相乘，所以實際上只要算黃色螢光筆那條路徑， 不必考慮其他條黑色路徑。 由此可以 16 = 2^4，所以有 4 個節點，只需計算 4次。 此時又可推導出 計算複雜度為： O(logn) （log 以 2 為底。） 用 C++ 實現的程式碼我放在 這裡 有興趣的可以直接拿來用，不用再造車輪了xD 感謝各位