<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Awaits on Medium]]></title>
        <description><![CDATA[Stories by Awaits on Medium]]></description>
        <link>https://medium.com/@jun94?source=rss-df1069eeeb53------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*XEX_2zTJakvrtDTOYJzNzw.png</url>
            <title>Stories by Awaits on Medium</title>
            <link>https://medium.com/@jun94?source=rss-df1069eeeb53------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 18:34:19 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@jun94/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[[MMDet3D] How to Infer — 3D Box Coordinates]]></title>
            <link>https://medium.com/jun94-devpblog/mmdet3d-how-to-infer-3d-box-coordinates-55c1fa0e57e2?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/55c1fa0e57e2</guid>
            <category><![CDATA[3d-object-detection]]></category>
            <category><![CDATA[mmdetection]]></category>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[perception]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Mon, 08 Apr 2024 22:59:03 GMT</pubDate>
            <atom:updated>2024-04-12T12:50:54.457Z</atom:updated>
            <content:encoded><![CDATA[<h3>[MMDet3D] How to Infer — 3D Box Coordinates</h3><p>In this article, we will go over how to use MMDet3D in order to retrieve predictions, particularly actual coordinate values of predicted 3D bounding-box, from a trained model.</p><p>I would like to kindly forward those readers who haven’t read the <a href="https://medium.com/jun94-devpblog/mmdet3d-how-to-infer-plotting-a7d5a56f244c">previous article</a> to go over it as this one is latter part of it.</p><p><a href="https://medium.com/jun94-devpblog/mmdet3d-how-to-infer-plotting-a7d5a56f244c">[MMDet3D] How to Infer — Plotting</a></p><p>Same as the last article, it assumes the followings:</p><ul><li><a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/"><em>MMDet3D</em></a>, version 1.4.0<em>, </em>is already installed.</li><li>Task is Monocular 3D Object detection where an image is given as input to model.</li><li><a href="https://github.com/open-mmlab/mmdetection3d/tree/main/configs/fcos3d"><em>FCOS3D</em></a> is chosen as a 3D object detector.</li><li>nuScenes Dataset is placed under PROJECT_ROOT/data.</li></ul><h3>What format are 3D Boxes are represented in?</h3><p>3D bounding boxes in 3D space can be represented in various formats. Popular ones could be either 8-corner(x, y, z) or (centroid, dimension, orientation).</p><h4>8-corner(x, y, z) Format</h4><ul><li>8-corner is intuitive format to represent a 3D box as it simply express 3D coordinates (x, y, z) for each 8 corner points of the box.</li><li>While it is simple and is not in need of any further decoding, one has to keep tracking the order of 8 points. Once the order gets mixed up, one might struggle to figure out what points define what face of 3D box.</li><li>Another disadvantage of this format is the memory usage. Since we are talking about 8 corner points of 3D box, it requires array of shape (8, 3) for individual box. <strong>When compared to (centroid, dimension, orientation) format, this consumes notably more space to store the box information.</strong></li></ul><h4><em>(centroid, dimension, orientation) Format</em></h4><ul><li>This representation requires 7 values to express a 3D box. First three for center point (center x, center y, center z), next three for box size (size in x-axis, size in y-axis, size in z-axis) and lastly one for orientation (yaw).</li><li>As this way of representation only requires an array of shape (7), while 8-corner requires (8, 3), it can be more commonly observed in practice.</li><li><strong>Note that this representation also can take 9 values, instead of 7, when orientation is represented in three dimensions, namely roll, pitch and yaw.</strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tE0UTUML407CxfT08FLJJA.png" /><figcaption>3D Box represented with 9 values, from <a href="https://www.asam.net/index.php?eID=dumpFile&amp;t=f&amp;f=3876&amp;token=413e8c85031ae64cc35cf42d0768627514868b2f">OpenLabel concept paper</a></figcaption></figure><h4>Data class for 3D Box in MMDet3D</h4><p>As this articles address a 3D monocular detector, FCOS3D, the predicted 3D bounding boxes are preresented with respect to a camera, i.e., a special structure called <a href="https://mmdetection3d.readthedocs.io/en/latest/_modules/mmdet3d/structures/bbox_3d/cam_box3d.html#CameraInstance3DBoxes"><em>CameraInstance3DBoxes</em></a> is used.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DwSnGs0H9zkJp58Tag3Brg.png" /><figcaption>Illustration of visualized 3D boxes and respective raw data from class, CameraInstance3DBoxes.</figcaption></figure><p>Among all member variables of <a href="https://mmdetection3d.readthedocs.io/en/latest/_modules/mmdet3d/structures/bbox_3d/cam_box3d.html#CameraInstance3DBoxes"><em>CameraInstance3DBoxes</em></a><em>, </em>the ones I believe worth to mention are illustrated and described below. Those I personally found highly-useful are highlighted in bold.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*X8F3YrD0OKofctK-eNGdlA.png" /><figcaption>Visualization of member variables of the class, <em>CameraInstance3DBoxes</em>.</figcaption></figure><ul><li><strong><em>center(N, 3)</em></strong>: The center of bottom face of the 3D Box. Unlike our intuition, MMDet3D defines center of 3D Box as the center of bottom face following KITTI convention. See remark section below for further details. As <em>CameraInstance3DBoxes </em>handles multiple boxes simultaneously, <em>N</em> in shape stands for the number of boxes.</li><li><strong><em>dims(N, 3)</em></strong>: The size of 3D Box along each axis(x, y, z).</li><li><strong><em>yaw(N, 1)</em></strong>: The orientation of 3D Box with respect to the camera coordinate system.</li><li><em>gravity_center(N, 3)</em>: The ACTUAL center of 3D Box, computed as the ave.</li><li><em>bottom_center(N, 3)</em>: same as <em>center</em> above.</li><li><em>corners(N, 8)</em>: All 8 corner points of 3D Box.</li><li><em>bev(N, 5)</em>: Oriented 2D Box to represent top face of each 3D Box. As the 2D Box is oriented, 5 attributes, center point(x, y), dim(size_x, size_y) and rotation angle(yaw), are taken.</li></ul><p>While <em>CameraInstance3DBoxes </em>provides numerous methods, I would like to highlight one, overlaps.</p><ul><li><strong><em>overlaps(boxes1, boxes2, mode) -&gt; overlap_scores</em>: </strong>Computes the degree of overlap between two given boxes(or set, box-set 1 and box-set 2). Normally, the metric to measure how much two given boxes overlap is IoU(intersectino over union).</li><li><strong><em>points_in_boxes_part(points, boxes) -&gt; box_indices</em></strong><em>:</em> returns at which box the given points belong.</li></ul><h4>Remark</h4><p><em>Please Note that the center of each 3D box is the center of bottom face, following the convention from KITTI as is discussed in </em><a href="https://github.com/open-mmlab/mmdetection3d/issues/703"><em>here</em></a><em>.</em></p><ul><li>Thus, you might need additional conversion to get the actual center(gravity center) of the 3D box.</li><li>Luckily the calculation is rather minor, I attached a well established figure to get intuition regarding relative center below.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hOtt_VYUstXR5em2-oFyyA.png" /><figcaption>further details were discussed in <a href="https://github.com/open-mmlab/mmdetection3d/issues/703">here</a></figcaption></figure><p>It is also worth to mention that MMDet3D provides class to represent 3D Box in other coordinates system, e.g., LiDAR.</p><ul><li>Base Box3D class</li></ul><p><a href="https://mmdetection3d.readthedocs.io/en/latest/_modules/mmdet3d/structures/bbox_3d/base_box3d.html#BaseInstance3DBoxes">mmdet3d.structures.bbox_3d.base_box3d - MMDetection3D 1.4.0 documentation</a></p><ul><li>Box3D class for Camera coordinate system</li></ul><p><a href="https://mmdetection3d.readthedocs.io/en/latest/_modules/mmdet3d/structures/bbox_3d/cam_box3d.html#CameraInstance3DBoxes">mmdet3d.structures.bbox_3d.cam_box3d - MMDetection3D 1.4.0 documentation</a></p><ul><li>Box3D class for LiDAR coordinate system</li></ul><p><a href="https://mmdetection3d.readthedocs.io/en/latest/_modules/mmdet3d/structures/bbox_3d/lidar_box3d.html#LiDARInstance3DBoxes">mmdet3d.structures.bbox_3d.lidar_box3d - MMDetection3D 1.4.0 documentation</a></p><h3>How to Obtain Raw Data of Predicted 3D Boxes?</h3><h4>Prerequisite: Info.pkl Generation</h4><p>Before getting into the programming part to retrieve the inference result(3D box) from MMDet3D, let us make sure our dataset is properly prepared, i.e., pre-processed, following the link below.</p><p><a href="https://mmdetection3d.readthedocs.io/en/latest/advanced_guides/datasets/nuscenes.html">NuScenes Dataset - MMDetection3D 1.4.0 documentation</a></p><p>Once the pre-processing step is done, one can find their directory where nuScenes dataset is stored has changed as below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*f5e0STla_NkaJbuXyWrrfw.png" /><figcaption>After running mmdetection3d/tools/create_data.py</figcaption></figure><p>While this step does not change the essence of nuScenes, it conducts re-formatting of the dataset for the sake of easier accessibility and usage during data-loading stage.</p><p>The detailed description for contents stored in each pkl files can be found <a href="https://mmdetection3d.readthedocs.io/en/latest/advanced_guides/datasets/nuscenes.html#dataset-preparation">here</a>.</p><h4>Run Inference with Monocular 3D Detector, FCOS3D</h4><p>The following image gives an overview of this section, given an image what and how we obtain the inference results.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fOy8UgvKxoKGlh7CrNRbOw.png" /></figure><p>In general, running inference is as simple as a single command line:</p><pre>$python mmdetection3d/demo/mono_det_demo.py {IMG} {GT_INFO} {MODEL} {CKPT}</pre><p>where</p><ul><li><em>IMG</em>: input image to be fed into the <em>MODEL</em>.</li><li><em>GT_INFO</em>: special format in pkl, widely used in MMDet3D, that processed the ground-truth labels of original dataset. See section:Prerequisite.</li><li><em>MODEL</em>: config.py file which states all information regarding its architecture.</li><li><em>CKPT</em>: trained weights to be loaded for <em>MODEL</em>.</li></ul><p>An example for each argument is as follows,</p><ul><li><em>IMG</em>: mmdetection3d/demo/data/nuscenes/n015–2018–07–24–11–22–45+0800__CAM_BACK__1532402927637525.jpg</li><li><em>GT_INFO</em>: mmdetection3d/demo/data/nuscenes/n015–2018–07–24–11–22–45+0800.pkl</li><li><em>MODEL</em>:<em> </em>mmdetection3d/configs/fcos3d/fcos3d_r101-caffe-dcn_fpn_head-gn_8xb2–1x_nus-mono3d_finetune.py</li><li><em>CKPT</em>:<em> </em><a href="https://download.openmmlab.com/mmdetection3d/v0.1.0_models/fcos3d/fcos3d_r101_caffe_fpn_gn-head_dcn_2x8_1x_nus-mono3d_finetune/fcos3d_r101_caffe_fpn_gn-head_dcn_2x8_1x_nus-mono3d_finetune_20210717_095645-8d806dc2.pth">fcos3d_r101_caffe_fpn_gn-head_dcn_2x8_1x_nus-mono3d_finetune_20210717_095645–8d806dc2.pth</a></li></ul><p>While the above command is sufficient in general to run inference on various models, I happened to find some minor modification is required to <strong>run FCOS3D with nuScenes dataset at MMDet3D ver1.4.0</strong>.</p><p>To address this, I made my custom class, FCOS3DInferencer, which inherits the original MonoDet3DInferencer from MMDet3D as below.</p><pre>import mmengine<br>import numpy as np<br>from mmdet3d.apis.inferencers.base_3d_inferencer import InputsType, track<br>from mmdet3d.apis.inferencers.mono_det3d_inferencer import MonoDet3DInferencer<br>from mmdet3d.registry import INFERENCERS<br>from mmengine.config import Config<br>from mmengine.config.utils import MODULE2PACKAGE<br>from mmengine.fileio import get_file_backend, isdir, join_path, list_dir_or_file<br>import os.path as osp<br>from typing import Optional, Tuple, Union<br><br><br>@INFERENCERS.register_module(name=&quot;det3d-mono&quot;, force=True)<br>class FCOS3DInferencer(MonoDet3DInferencer):<br><br>    def __call__(<br>        self, inputs: InputsType, batch_size: int = 1, return_datasamples: bool = False, **kwargs<br>    ) -&gt; Optional[dict]:<br>        &quot;&quot;&quot;Call the inferencer.<br><br>        Args:<br>            inputs (InputsType): Inputs for the inferencer.<br>            batch_size (int): Batch size. Defaults to 1.<br>            return_datasamples (bool): Whether to return results as<br>                :obj:`BaseDataElement`. Defaults to False.<br>            **kwargs: Key words arguments passed to :meth:`preprocess`,<br>                :meth:`forward`, :meth:`visualize` and :meth:`postprocess`.<br>                Each key in kwargs should be in the corresponding set of<br>                ``preprocess_kwargs``, ``forward_kwargs``, ``visualize_kwargs``<br>                and ``postprocess_kwargs``.<br><br><br>        Returns:<br>            dict: Inference and visualization results.<br>        &quot;&quot;&quot;<br><br>        (<br>            preprocess_kwargs,<br>            forward_kwargs,<br>            visualize_kwargs,<br>            postprocess_kwargs,<br>        ) = self._dispatch_kwargs(**kwargs)<br><br>        if &quot;cam_type&quot; in preprocess_kwargs:<br>            cam_type = preprocess_kwargs.pop(&quot;cam_type&quot;)<br>        else:<br>            cam_type = visualize_kwargs[&quot;cam_type_dir&quot;]<br>        ori_inputs = self._inputs_to_list(inputs, cam_type=cam_type)<br>        inputs = self.preprocess(ori_inputs, batch_size=batch_size, **preprocess_kwargs)<br>        preds = []<br><br>        results_dict = {&quot;predictions&quot;: [], &quot;visualization&quot;: []}<br>        for data in track(inputs, description=&quot;Inference&quot;) if self.show_progress else inputs:<br>            preds.extend(self.forward(data, **forward_kwargs))<br>            visualization = self.visualize(ori_inputs, preds, **visualize_kwargs)<br>            results = self.postprocess(preds, visualization, return_datasamples, **postprocess_kwargs)<br>            # results_dict[&#39;predictions&#39;].extend(results[&#39;predictions&#39;]) # to prevent memory error, we disable this line.<br>            if results[&quot;visualization&quot;] is not None:<br>                results_dict[&quot;visualization&quot;].extend(results[&quot;visualization&quot;])<br>        return results_dict<br><br>    def _inputs_to_list(self, inputs: Union[dict, list], cam_type=&quot;CAM2&quot;, **kwargs) -&gt; list:<br>        &quot;&quot;&quot;Preprocess the inputs to a list.<br><br>        Preprocess inputs to a list according to its type:<br><br>        - list or tuple: return inputs<br>        - dict: the value with key &#39;img&#39; is<br>            - Directory path: return all files in the directory<br>            - other cases: return a list containing the string. The string<br>              could be a path to file, a url or other types of string according<br>              to the task.<br><br>        Args:<br>            inputs (Union[dict, list]): Inputs for the inferencer.<br><br>        Returns:<br>            list: List of input for the :meth:`preprocess`.<br>        &quot;&quot;&quot;<br>        if isinstance(inputs, dict):<br>            assert &quot;infos&quot; in inputs<br>            infos = inputs.pop(&quot;infos&quot;)<br><br>            if isinstance(inputs[&quot;img&quot;], str):<br>                img = inputs[&quot;img&quot;]<br>                backend = get_file_backend(img)<br>                if hasattr(backend, &quot;isdir&quot;) and isdir(img):<br>                    # Backends like HttpsBackend do not implement `isdir`, so<br>                    # only those backends that implement `isdir` could accept<br>                    # the inputs as a directory<br>                    filename_list = list_dir_or_file(img, list_dir=False)<br>                    inputs = [{&quot;img&quot;: join_path(img, filename)} for filename in filename_list]<br><br>            if not isinstance(inputs, (list, tuple)):<br>                inputs = [{&quot;img&quot;: img_path} for img_path in inputs[&quot;img&quot;]]<br><br>            # get cam2img, lidar2cam and lidar2img from infos<br>            info_list = mmengine.load(infos)[&quot;data_list&quot;]<br>            assert len(info_list) == len(inputs)<br>            for index, input in enumerate(inputs):<br>                data_info = info_list[index]<br>                img_path = data_info[&quot;images&quot;][cam_type][&quot;img_path&quot;]<br>                if isinstance(input[&quot;img&quot;], str) and osp.basename(img_path) != osp.basename(input[&quot;img&quot;]):<br>                    raise ValueError(f&quot;the info file of {img_path} is not provided.&quot;)<br>                cam2img = np.asarray(data_info[&quot;images&quot;][cam_type][&quot;cam2img&quot;], dtype=np.float32)<br>                lidar2cam = np.asarray(data_info[&quot;images&quot;][cam_type][&quot;lidar2cam&quot;], dtype=np.float32)<br>                if &quot;lidar2img&quot; in data_info[&quot;images&quot;][cam_type]:<br>                    lidar2img = np.asarray(data_info[&quot;images&quot;][cam_type][&quot;lidar2img&quot;], dtype=np.float32)<br>                else:<br>                    assert cam2img.shape == (3, 3)<br>                    cam2img_ = np.eye(4)<br>                    cam2img_[:3, :3] = cam2img<br>                    lidar2img = cam2img_ @ lidar2cam<br><br>                input[&quot;cam2img&quot;] = cam2img<br>                input[&quot;lidar2cam&quot;] = lidar2cam<br>                input[&quot;lidar2img&quot;] = lidar2img<br>        elif isinstance(inputs, (list, tuple)):<br>            # get cam2img, lidar2cam and lidar2img from infos<br>            for input in inputs:<br>                assert &quot;infos&quot; in input<br>                infos = input.pop(&quot;infos&quot;)<br>                info_list = mmengine.load(infos)[&quot;data_list&quot;]<br>                assert len(info_list) == 1, &quot;Only support single sample info&quot; &quot;in `.pkl`, when inputs is a list.&quot;<br>                data_info = info_list[0]<br>                img_path = data_info[&quot;images&quot;][cam_type][&quot;img_path&quot;]<br>                if isinstance(input[&quot;img&quot;], str) and osp.basename(img_path) != osp.basename(input[&quot;img&quot;]):<br>                    raise ValueError(f&quot;the info file of {img_path} is not provided.&quot;)<br>                cam2img = np.asarray(data_info[&quot;images&quot;][cam_type][&quot;cam2img&quot;], dtype=np.float32)<br>                lidar2cam = np.asarray(data_info[&quot;images&quot;][cam_type][&quot;lidar2cam&quot;], dtype=np.float32)<br>                if &quot;lidar2img&quot; in data_info[&quot;images&quot;][cam_type]:<br>                    lidar2img = np.asarray(data_info[&quot;images&quot;][cam_type][&quot;lidar2img&quot;], dtype=np.float32)<br>                else:<br>                    lidar2img = cam2img @ lidar2cam<br>                input[&quot;cam2img&quot;] = cam2img<br>                input[&quot;lidar2cam&quot;] = lidar2cam<br>                input[&quot;lidar2img&quot;] = lidar2img<br><br>        return list(inputs)<br><br>    def _load_model_from_metafile(self, model: str) -&gt; Tuple[Config, str]:<br>        &quot;&quot;&quot;Load config and weights from metafile.<br><br>        Args:<br>            model (str): model name defined in metafile.<br><br>        Returns:<br>            Tuple[Config, str]: Loaded Config and weights path defined in<br>            metafile.<br>        &quot;&quot;&quot;<br>        model = model.lower()<br><br>        assert self.scope is not None, &quot;scope should be initialized if you want &quot; &quot;to load config from metafile.&quot;<br>        assert self.scope in MODULE2PACKAGE, f&quot;{self.scope} not in {MODULE2PACKAGE}!,&quot; &quot;please pass a valid scope.&quot;<br><br>        repo_or_mim_dir = CustomMonoDet3DInferencer._get_repo_or_mim_dir(self.scope)<br>        for model_cfg in CustomMonoDet3DInferencer._get_models_from_metafile(repo_or_mim_dir):<br>            model_name = model_cfg[&quot;Name&quot;].lower()<br>            model_aliases = model_cfg.get(&quot;Alias&quot;, [])<br>            if isinstance(model_aliases, str):<br>                model_aliases = [model_aliases.lower()]<br>            else:<br>                model_aliases = [alias.lower() for alias in model_aliases]<br>            if model_name in model or model in model_aliases:<br>                cfg = Config.fromfile(osp.join(repo_or_mim_dir, model_cfg[&quot;Config&quot;]))<br>                weights = model_cfg[&quot;Weights&quot;]<br>                weights = weights[0] if isinstance(weights, list) else weights<br>                return cfg, weights<br>        raise ValueError(f&quot;Cannot find model: {model} in {self.scope}&quot;)</pre><p>While most of the code remains the same as the original, the changes I made are the following two:</p><ul><li>Removed hard-coded <em>cam_type</em>, CAM2 which was used only for KITTI dataset.</li><li>Disabled <em>results_dict</em> in the function, <em>__call__</em>.</li></ul><p>Note that I intentionally disabled <em>results_dict </em>as when the large number of images was given, e.g., entire nuScenes dataset, the inference results keep stack up and lead to memory overflow. To prevent it, I simply commented out the line where <em>result_dict</em> is updated.</p><p>For those who might worry that this modification won’t get you the inference results, the inference results will be stored in the specified output directory, which you can specify as argument for mono_det_demo.py, regardless of this modification.</p><p><strong>Any corrections, suggestions, and comments are welcome</strong></p><h3>Reference</h3><p>[1] <a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/get_started.html#get-started">MMDet3D </a>— <a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/get_started.html#get-started">Installation</a></p><p>[2] <a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/user_guides/visualization.html">MMDet3D — Visualization</a></p><p>[3] <a href="http://baseinstance3dboxes/">MMDet3D — Structure.BBOX</a></p><p>[4]<a href="https://mmdetection3d.readthedocs.io/en/v1.0.0rc0/tutorials/coord_sys_tutorial.html"> MMDet3D — CoordinateSystem</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=55c1fa0e57e2" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jun94-devpblog/mmdet3d-how-to-infer-3d-box-coordinates-55c1fa0e57e2">[MMDet3D] How to Infer — 3D Box Coordinates</a> was originally published in <a href="https://medium.com/jun94-devpblog">Learning</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[MMDet3D] How to Infer — Plotting]]></title>
            <link>https://medium.com/jun94-devpblog/mmdet3d-how-to-infer-plotting-a7d5a56f244c?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/a7d5a56f244c</guid>
            <category><![CDATA[mmdetection]]></category>
            <category><![CDATA[perception]]></category>
            <category><![CDATA[object-detection]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Sun, 31 Mar 2024 07:58:23 GMT</pubDate>
            <atom:updated>2024-03-31T07:58:23.732Z</atom:updated>
            <content:encoded><![CDATA[<h3>[MMDet3D] How to Infer — Plotting</h3><p>In this article, we will go over how to use MMDet3D in order to retrieve inference/predictions from a trained model.</p><p>Typically, inference results include raw prediction (coordinates of individual 3D bounding boxes) and visualization (3D bounding boxes plotted on input image/point cloud).</p><p>As this article assumes readers to have MMDet3D installed in their environment, I leave a <a href="https://medium.com/jun94-devpblog/mmdet3d-how-to-install-f4012150c0d0"><strong>link</strong></a> where one can find detailed guide regarding installation of MMDet3D for those who haven’t done it yet.</p><p>For the sake of simplicity, I used <a href="https://github.com/open-mmlab/mmdetection3d/tree/main/configs/fcos3d"><em>FCOS3D</em></a> as a 3D detector and <a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/">MMDet3D ver1.4.0,</a> but the general flow should remain more or less the same for the other detectors and versions.</p><ul><li>Note that this article does not address theoretical or practical parts of the monocular 3D detector, <em>FCOS3D</em> as it is beyond the scope.</li><li>One can simply accept it as a 3D detector which takes a single image as an input and outputs a 3D bounding boxes for objects presented in the image.</li></ul><p>After this tutorial, you would be able to obtain images like below on your machine.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Eil1MPADiIt9rWFt7EAGfQ.png" /><figcaption>Inference results of FCOS3D, plotted on input images</figcaption></figure><h3>How to Obtain Visualized Outputs?</h3><p>While retrieving the 3D box proposals from a detector and overlaying them on an image are not a simple task (at least, not a few lines of coding), fortunately MMDet3D provides built-in method(s) to make this job easy.</p><p>The ready-made APIs support various types of inputs, e.g., image and point cloud.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Y0mtqY-84u8ZHRQI5D75zg.png" /></figure><ul><li>Drawing point cloud on the image</li><li>Drawing 3D Boxes on Point Cloud</li><li>Drawing Projected 3D Boxes on Image</li></ul><p>As APIs for point cloud as an input are kindly explained in many other articles, I will focus on when an image is given as input.</p><p>The main workflow is just the same as when it was point cloud, i.e., we will use tools/test.py bu<strong>t with different arguments. </strong>The entire command is as simple as below.</p><pre>cd YOUR_PROJECT_ROOT<br>python mmdetection3d/tools/test.py mmdetection3d/configs/fcos3d/fcos3d_r101-caffe-dcn_fpn_head-gn_8xb2-1x_nus-mono3d_finetune.py ckpt/fcos3d/fcos3d_r101_caffe_fpn_gn-head_dcn_2x8_1x_nus-mono3d_finetune_20210717_095645-8d806dc2.pth --show --show-dir result/fcos3d --task mono_det</pre><p>Note that the command above has several prerequisites.</p><ol><li>mmdetection3d(MMDet3D) is placed right under your project ROOT.</li><li>nuScenes Dataset is downloaded (or symbolic-linked) and placed under PROJECT_ROOT/data, as described in <a href="https://mmdetection3d.readthedocs.io/en/latest/advanced_guides/datasets/nuscenes.html">here</a>. <strong>Make sure that the relavant pkl files are also generated</strong> from original nuScenes Dataset following the section ‘Dataset Preperation’ of the link, the command would not run otherwise.</li><li>As we are using FCOS3D as a 3D detector, ckpt file from which MMDet3D loads the pre-trained weights should be downloaded in advance.</li></ol><ul><li>In my case, I downloaded the weight from <a href="https://download.openmmlab.com/mmdetection3d/v0.1.0_models/fcos3d/fcos3d_r101_caffe_fpn_gn-head_dcn_2x8_1x_nus-mono3d/fcos3d_r101_caffe_fpn_gn-head_dcn_2x8_1x_nus-mono3d_20210715_235813-4bed5239.pth">here</a> and placed it under PROJECT_ROOT/ckpt/fcos3d.</li><li>See the directory structure below that I used to ran this tutorial.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0Ohr4qFPHeVwIOQyGBvF3A.png" /><figcaption>Directory Structure</figcaption></figure><p>Once the prerequsites were met and the command ran,<strong> you can find the inference results of FCOS3D given nuScenes image under </strong>PROJECT_ROOT/work_dirs/CONFIG_NAME/DATE/result/fcos3d.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*V9AswsKxmeziIbCp8MFqlw.png" /></figure><ul><li>CONFIG_NAME is fcos3d_r101-caffe-dcn_fpn_head-gn_8xb2–1x_nus-mono3d_finetune, unless you specified otherwise in the command.</li><li>DATE is when you ran the command.</li></ul><p>So far, I have addressed how to plot the inference results upon the input image, <strong>but how to retrieve each coordinates of predicted bounding boxes is unhandled</strong>. In fact, to achieve that we need different workflow.</p><p>I will talk about that in the next chapter.</p><p><strong>Any corrections, suggestions, and comments are welcome</strong></p><h3>Reference</h3><p>[1] <a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/get_started.html#get-started">MMDet3D </a>— <a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/get_started.html#get-started">Installation</a></p><p>[2] <a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/user_guides/visualization.html">MMDet3D — Visualization</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a7d5a56f244c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jun94-devpblog/mmdet3d-how-to-infer-plotting-a7d5a56f244c">[MMDet3D] How to Infer — Plotting</a> was originally published in <a href="https://medium.com/jun94-devpblog">Learning</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[MMDet3D] How to install]]></title>
            <link>https://medium.com/jun94-devpblog/mmdet3d-how-to-install-f4012150c0d0?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/f4012150c0d0</guid>
            <category><![CDATA[3d-object-detection]]></category>
            <category><![CDATA[pytorch]]></category>
            <category><![CDATA[perception]]></category>
            <category><![CDATA[mmdetection]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Sun, 31 Mar 2024 02:49:58 GMT</pubDate>
            <atom:updated>2024-03-31T02:49:58.596Z</atom:updated>
            <content:encoded><![CDATA[<h3>What is MMDet3D?</h3><p>While PyTorch is unarguably one of the ground-winning libraries in the field of deep learning, it does not provide built-in 3D perception models by nature. And therefore, mostly it is up to researchers to implement all modules(pre- and post-processings, anchors, etc.) of complicated 3D perception pipeline. Clearly, it is not impossible to implement on their own, but it is time-consuming job and could easily distract them from the core job, which is to find research novelties. See the exemplary perception module below and imagine when one needs to code individual components of the model themselves.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*m9QRzyj69GJGiAansdJD8Q.png" /><figcaption>Architecture overview of <a href="https://arxiv.org/abs/2307.14620">NeRF-Det</a></figcaption></figure><p>MMDetection3D (MMDet3D) is an open-source toolbox, specifically designed to supply built-in models for 3D object detection tasks. It provides a collection of SOTA algorithms and models so that researchers could purely focus on what they are interested in, instead of trouble shooting through individual components of 3D perception system.</p><p>One can find the list of provided models in the <a href="https://github.com/open-mmlab/mmdetection3d">link</a>.</p><h3>How to Install MMDet3D?</h3><p>The general installation guide is well explained in their official <a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/get_started.html">website</a>.</p><p>However the detail of the instruction for individual systems could vary.</p><p>Therefore, I will take this chance to describe how I installed MMDet3D <strong>v1.4.0</strong> in my system(<strong>Ubuntu20.04, GTX3090</strong>).</p><p>The following is the command lines I used based on conda environment named <em>openmmlab</em> with python3.8.</p><pre># build virtual environment of python3.8 with name openmmlab using conda<br>$conda create --name openmmlab python=3.8 -y<br>$conda activate openmmlab<br><br># install torch-relavant libraries<br>$conda install pytorch==1.12.1 torchvision==0.13.1 torchaudio==0.12.1 cudatoolkit=11.3 -c pytorch<br><br># use the package manager mim to install openmmlab-relavant libraries with specific versions.<br>$pip install -U openmim<br>$mim install mmengine==0.10.3<br>$mim install mmcv==2.1.0<br>$mim install mmdet==3.3.0<br><br># install mmdetection3d ver 1.4.0<br>$git clone https://github.com/open-mmlab/mmdetection3d.git -b dev-1.4.0<br>$cd mmdetection3d<br>$pip install -v -e .<br># &quot;-v&quot; means verbose, or more output<br># &quot;-e&quot; means installing a project in edtiable mode,<br># thus any local modifications made to the code will take effect without reinstallation.<br><br># install additional libraries required to run particular models with sparse convolution.<br>$pip install cumm-cu113<br>$pip install spconv-cu113</pre><p>Note that I specified cuda version when isntalling cumm and spconv, i.e., cumm-cu113. This is because those libraries require you to specify which CUDA version the virtual environment is running on. Mine was 11.3 as cudatoolkit=11.3, and thus, I gave the command pip install cumm-cu113.</p><p>Once you complete the installation instructions above, your virtual environment must have libraries installed as below.</p><pre>conda activate openmmlab<br>pip list | grep mm</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/524/1*-88OoxNKDpykiIHtpMUCtw.png" /></figure><h3>How to Ensure MMDet3D is Successfully Installed?</h3><p>To confirm it is well installed, MMDet3D provides some demo scripts.</p><p>By conducting inference on a sample data with pre-trained 3D detector, one can verify the installation of MMDet3D.</p><p>Assuming you installed MMDet3D at your project ROOT, first we download pre-trained weights for a 3D detector, PointPillar.</p><pre>mim download mmdet3d -config pointpillars_hv_secfpn_8xb6–160e_kitti-3d-car  -dest .</pre><p>This command should get the config file and pre-trained weight for PointPillar installed at the current working directory.</p><ul><li>config: pointpillars_hv_secfpn_8xb6-160e_kitti-3d-car.py</li><li>weight: hv_pointpillars_secfpn_6x8_160e_kitti-3d-car_20220331_134606-d42d15ed.pth</li><li>If you want to download it at another directory, simply give the path of the directory to the argument, <em>—dest.</em></li></ul><p>Once downloaded, we are ready to conduct the demo to run PointPillar on a sample data by the command below.</p><pre>cd mmdetection3d<br>python demo/pcd_demo.py demo/data/kitti/000008.bin pointpillars_hv_secfpn_8xb6–160e_kitti-3d-car.py hv_pointpillars_secfpn_6x8_160e_kitti-3d-car_20220331_134606-d42d15ed.pth --show</pre><p>If all aforementioned requirements were fulfilled, this should plot the point cloud of the given sample data along with 3D bounding boxes predicted by PointPillar, as shown below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_tKpdQBWO28UpJ_2O2NprA.png" /></figure><h3>Reference</h3><p>[1] <a href="https://mmdetection3d.readthedocs.io/en/v1.4.0/get_started.html#get-started">MMDet3D</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f4012150c0d0" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jun94-devpblog/mmdet3d-how-to-install-f4012150c0d0">[MMDet3D] How to install</a> was originally published in <a href="https://medium.com/jun94-devpblog">Learning</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[DL] 13. Convolution and Pooling Variants (Dilated Convolution, SPP, ASPP)]]></title>
            <link>https://medium.com/jun94-devpblog/dl-13-convolution-and-pooling-variants-dilated-convolution-spp-aspp-a954a282ff5c?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/a954a282ff5c</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[neural-networks]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Mon, 28 Dec 2020 19:46:35 GMT</pubDate>
            <atom:updated>2020-12-28T19:46:35.685Z</atom:updated>
            <content:encoded><![CDATA[<h3>1. Dilated Convolution</h3><p>Dilated convolution, which is also often called atrous convolution, was introduced in 2016 ICLR. Its major idea is that when performing convolution, not taking a look at directly adjacent pixels, but further away pixels by a certain distance.</p><p>This distance is called ‘Dilation rate <strong><em>r</em></strong>,’ and the dilated convolution can be mathematically represented as follows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/486/1*nNK3zGS-9i8wwr5Jc5tI8A.png" /><figcaption><strong>Equation 1. Dilated Convolution with dilation rate r</strong></figcaption></figure><p>From the equation of standard convolution, only the term for dilation rate <strong><em>r</em></strong> is added, and as one might notice, if <strong><em>r</em></strong> is one, then the <em>eq 1</em> is just a standard convolution.</p><p>Then what is the role of dilatation rate? This question can be well answered with the visualization below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/395/0*iGWye7po2fI4QX3Y.gif" /><figcaption><strong>Standard convolution, when r = 1</strong></figcaption></figure><p>As mentioned before, dilated convolution becomes the standard convolution if r = 1.</p><p>However, things get different if r is larger than one. The following illustrates when r = 2, and we can observe that the convolution computes the weighted sum for pixels, which are far away by a distance of 2 to each other, in the input.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/395/0*vwOEMi8LRHGx7Mt6.gif" /><figcaption><strong>Dilated Convolution, when r = 2</strong></figcaption></figure><p><strong>What is advantageous of using dilated convolution instead of the standard one?</strong></p><p>As we have seen, the dilated convolution has an effect of increasing the receptive field without increasing computation. In other words, it can achieve the result of pooling without additional computation and losing the resolution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0OEU2VQHKtJW-kMiiynIWg.png" /><figcaption><strong>Figure 1. Illustration of 3x3 Dilated convolution. Left panel: dilation rate r = 1, equivalent to the normal convolution, center panel: dilation rate r=2, right panel: r=3, from </strong><a href="https://www.researchgate.net/figure/Dilated-convolution-On-the-left-we-have-the-dilated-convolution-with-dilation-rate-r_fig2_320195101"><strong>link</strong></a></figcaption></figure><h3><strong>2. Spatial Pyramid Pooling (SPP)</strong></h3><p>Given feature maps from previous convolution layers, SPP performs max-pooling operations multiple times with increasing kernel sizes. Afterward, each pooling operation results are transformed into a vector representation, and those vector representations are concatenated to produce the final fixed-length representation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IvBu9n0ohRLQM1VSHUYBCg.png" /><figcaption><strong>Figure 2. Illustration of the Spatial Pyramid Pooling (SPP), from [1]</strong></figcaption></figure><p>With multiple pooling layers at different scales, it captures information from varying image scale, leading to achieving the robustness to varying image scales. As a result, <em>SPP</em> creates a multi-scale feature representation that can be used for classification in the later parts of the network.</p><h3>3. Atrous Spatial Pyramid Pooling (ASPP)</h3><p>Another approach to building a multi-scale representation using the idea of looking at input image at varying scales is the <em>Atrous Spatial Pyramid Pooling (ASPP). </em>In other words,<em> ASPP </em>is an extension of the<em> SPP</em> concept making use of dilated convolutions instead of max pooling.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Eo9D404sc3gyr-CkGou0rQ.png" /><figcaption><strong>Figure 3. Illustration of ASPP, from [1]</strong></figcaption></figure><p>The difference is that ASPP does not decrease the resolution, meaning that the input and output sizes of ASPP are the same since the max-pooling operation does not exist in ASPP.</p><p>More specifically, while the output of SPP is in form of a single vector, the output of ASPP remains in form of 2D feature maps, as is shown below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/598/1*yI37ooOcLuyVLepcgYphaA.png" /><figcaption><strong>Figure 4. Illustration of ASPP(2)</strong></figcaption></figure><p>Further, as the dilated convolutions replace the standard convolutions in ASPP, the receptive fields are increased without extra computation.</p><h3>Reference</h3><p>[1] <a href="https://www.vision.rwth-aachen.de/courses/">RWTH Aachen, computer vision group</a></p><p><strong>Any corrections, suggestions, and comments are welcome.</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a954a282ff5c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jun94-devpblog/dl-13-convolution-and-pooling-variants-dilated-convolution-spp-aspp-a954a282ff5c">[DL] 13. Convolution and Pooling Variants (Dilated Convolution, SPP, ASPP)</a> was originally published in <a href="https://medium.com/jun94-devpblog">Learning</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[DL] 12. Unsampling: Unpooling and Transpose Convolution]]></title>
            <link>https://medium.com/jun94-devpblog/dl-12-unsampling-unpooling-and-transpose-convolution-831dc53687ce?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/831dc53687ce</guid>
            <category><![CDATA[deep-learning]]></category>
            <category><![CDATA[neural-networks]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Mon, 28 Dec 2020 15:54:25 GMT</pubDate>
            <atom:updated>2020-12-28T15:54:25.024Z</atom:updated>
            <content:encoded><![CDATA[<h3>1. Motivation</h3><p>When we study neural network architectures based on encoder and decoder, it is commonly observed that the network performs <em>downsampling</em> in the encoder and <em>upsampling</em> inside the decoder, as is illustrated in <em>Fig 1</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C1PsnhxVHQx6MW1xcYbjrg.png" /><figcaption><strong>Figure 1. Fully-Convolutional Network for Segmentation with encoder-decoder structure, from [7]</strong></figcaption></figure><p>Methods for downsampling are <em>max pooling</em> and <em>strided convolution</em>. However, what are the available approaches for upsampling?</p><p>This article mainly addresses two upsampling methods based on pooling and convolution, respectively.</p><h3>2. Unpooling</h3><p>The first type of unsampling is <em>Unpooling</em> which takes the idea of pooling. The max-pooling operation takes only the largest response from each sub-divided regions of the feature map. <em>Fig 2 </em>shows the max pooling operation given <em>4⨯4 </em>input feature map.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/612/1*jCUlstd7na77HhBcfI2_3w.png" /><figcaption><strong>Figure 2. Illustration of Maxpooling, from [1, 7]</strong></figcaption></figure><p>Unpooling, as its name implies, attempts to perform exactly the opposite, restoring the size of original input feature map (in Fig2, from <em>2⨯2</em> to <em>4⨯4</em>).</p><p>To do this, there are three ways. For the sake of simplicity and consistency, I assume the size of original feature map is <em>4⨯4, </em>and it becomes <em>2⨯2 </em>after max pooling.</p><h4>2.1 Nearest-Neighbor</h4><p>Nearest-Neighbor is the simplest approach to upsample. It copies a pixel value (response) of input feature map to all pixels in the corresponding sub-region of output.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/682/1*9N9FVYalaVAk-aalcBVYaA.png" /><figcaption><strong>Figure 3. Illustration of Nearest-Neighbor, from [1, 7]</strong></figcaption></figure><p>Although its simplicity, the problem of this approach is that <strong>the output structure becomes blocky</strong> as all pixels in each subregion have the same value.</p><h4>2.2 Bed of Nails</h4><p>Another de-pooling method, the Bed-of-Nails operation put an input feature response (element) in the top-left corner of the corresponding sub-region of de-pooling output, and it sets all the other elements in the sub-region to zero.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/692/1*LQVVqK8YJ4ndcU6NS4UOxA.png" /><figcaption><strong>Figure 4. Illustration of Bed of Nails, from [1, 7]</strong></figcaption></figure><p>By doing so, it achieves the fine-grained output structure. However, the <strong>upsampled elements always have a fixed location</strong>, which is the upper-left corner in the case of <em>Fig 4</em>.</p><h4>2.3 Max Unpooling</h4><p>In order to supplement the problem of <em>Bed of Nails</em>, <em>Max Unpooling</em> is introduced. While <em>Max Unpooling </em>performs upsampling in a similar manner as <em>Bed of Nails</em>, it remembers the indices of where the largest elements come from before max pooling. And this information is used later on when <em>Max Unpooling</em> is performed to place the elements in the positions of each sub-region where they are previously located before max pooling.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*b0NUJ-7IJnrljrzAc07BzQ.png" /><figcaption><strong>Figure 5. Illustration of Max Unpooling, from [11]</strong></figcaption></figure><h3>3. Transpose Convolution</h3><p>We have taken a look at upsampling approaches based on unpooling. As one might notice, the previously mentioned three methods are fixed numerical equations (functions) and there is no learning taking place.</p><p>Another type of upsampling, which makes use of learning, is called <em>transpose convolution.</em></p><p>Let’s recall first the conventional convolution with the following example. Given the image and filter, it computes the dot product for overlapping pixels in the window. Subsequently, the window moves 2 pixels (as stride is 2) and repeats the computing dot product. In the backpropagation step, the parameters in the filter get updated and learn from mistakes (error) they made.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Z_uMoY0yV2OCPEgsCLaMjQ.png" /><figcaption><strong>Figure 6. Illustration of convolution operation with 3x3 filter and stride of 2, adapted from [1, 7, 11]</strong></figcaption></figure><p>As a result of strided convolution operation, the resolution decreases from <em>4⨯4 </em>to<em> 2⨯2.</em></p><p>In order to undo the reduction in resolution and upscale it back to the original size, The transpose convolution is introduced. For better understanding, let’s take a look at the 1D example of transpose convolution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Cti98FtmLNJEgWdQ0HorRQ.png" /><figcaption><strong>Figure 7. Illustration of 1D transpose convolution, from [1, 7, 11]</strong></figcaption></figure><p>Suppose we have<em> 2⨯1</em> input, <em>3⨯1</em> filter, and transpose convolution with the stride of 2. Then the output of the operation has the size of <em>5⨯1</em>, which is obtained by copying each input value weighted by the filter, summing the overlaps, as is illustrated in <em>Fig 7</em>.</p><p>Clearly, the filter parameters, x,y, and z, are updated in the backpropagation step, and this is why the transpose convolution is a learnable upsampling approach.</p><blockquote>Note that if the stride is one, then the output size becomes 4⨯1.</blockquote><h4>3.1 Why it is named ‘transpose’ convolution?</h4><p>To answer this question, we need to represent the normal convolution operation in a form of matrix multiplication.</p><p>Assume we convolve the <em>4⨯1</em> input with the <em>3⨯1</em> filter and stride is set to one, as is shown below. We can represent this convolution operation as a multiplication of the same input with the matrix <strong><em>X.</em></strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-TExsLdWKXaX4Hx2WkaUjA.png" /></figure><p>After the convolution, the output size is the same as input size, which is <em>4⨯1, </em>since our stride is set to one.</p><p>What happens if we compute the same multiplication but with transposed <strong><em>X</em></strong>?</p><p>The following is the result. As we can observe, the output size becomes <em>5⨯1</em>, when the input size remains <em>4⨯1.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/746/1*y7uryFzm1J4M_883ilu3vg.png" /></figure><p>The behavior of transpose convolution becomes more clear when we have an example with the stride of 2.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*aOL_Tcuj8PCaOQ0ToELyJA.png" /></figure><h3>Reference</h3><p>[1] <a href="https://www.vision.rwth-aachen.de/courses/">RWTH Aachen, computer vision group</a></p><p>[2] <a href="http://vision.cs.utexas.edu/376-spring2018/">CS 376: Computer Vision of Prof. <strong>Kristen Grauman</strong></a></p><p>[3] <a href="https://homes.cs.washington.edu/~seitz/"><strong>S. Seitz</strong></a><br>[4] <a href="https://www.amazon.de/Computer-Vision-Approach-David-Forsyth/dp/013608592X"><strong>Forsyth &amp; Ponce</strong></a></p><p>[5] Prof. <a href="https://slazebni.cs.illinois.edu/"><strong>Svetlana Lazebnik</strong></a></p><p>[6] <a href="https://scholar.google.com/citations?user=5hJNWakAAAAJ&amp;hl=en">Prof <strong>M. Irani</strong></a> and <strong>R.</strong> <strong>Basri</strong></p><p>[7]<a href="https://scholar.google.com/citations?user=rDfyQnIAAAAJ&amp;hl=en"> Prof. <strong>Li fei-fei</strong></a></p><p>[8] <a href="https://scholar.google.com/citations?user=jkm1ipUAAAAJ&amp;hl=en">Denis Simakov</a></p><p>[9] <a href="https://scholar.google.com/citations?user=d97bGd8AAAAJ&amp;hl=ko">Alexej Efros</a></p><p>[10] <a href="https://scholar.google.com/citations?user=s1IAWfgAAAAJ&amp;hl=en">Prof. Krystian Mikolajczyk</a></p><p>[11] <a href="https://www.programmersought.com/article/709640128/">upsampling</a></p><p><strong>Any corrections, suggestions, and comments are welcome</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=831dc53687ce" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jun94-devpblog/dl-12-unsampling-unpooling-and-transpose-convolution-831dc53687ce">[DL] 12. Unsampling: Unpooling and Transpose Convolution</a> was originally published in <a href="https://medium.com/jun94-devpblog">Learning</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[CV] 14.  Image Alignment (Transformation Estimation)]]></title>
            <link>https://jun94.medium.com/cv-14-image-alignment-transformation-estimation-4006f28e103?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/4006f28e103</guid>
            <category><![CDATA[computer-vision]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Wed, 23 Dec 2020 23:18:34 GMT</pubDate>
            <atom:updated>2020-12-23T23:18:34.135Z</atom:updated>
            <content:encoded><![CDATA[<h3>[CV] 14. Image Alignment (Transformation Estimation)</h3><h3>1. Recap</h3><p>Previously, we have seen how local features are extracted from an image, using scale-invariant local feature descriptors such as <em>Harris-Laplace</em> and <em>SIFT</em>. After extracting local features individually from two images, the local features can be paired by searching the one with the highest similarity.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dcuStgR_Vr1P9i3fNpSf4w.png" /><figcaption><strong>Figure 1. pairs of interest points independently extracted from two images of the same object, from [1]</strong></figcaption></figure><p>More specifically, the basic matching algorithm is as follows:</p><p>(1) Detect interest points in two images using local feature descriptors.</p><p>(2) For each interest point, extract region (patch) and compute a local feature representation.</p><p>(3) Compare one feature from image 1 to every feature in image 2 and select one which shows the highest similarity.</p><p>(4) Repeat <em>step 2</em> for all interest points in image 1.</p><p>(5) return the pairs of interest points.</p><p><strong>What can we do with the pairs?</strong></p><p>One application is to estimate the transformation between images so that images can be stitched (aligned).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wTusSB0z8sGVnXoeEgdT9Q.png" /><figcaption><strong>Figure 2. Image stitching, from [1, 8]</strong></figcaption></figure><p>From now on, this article will address how to find the <strong>transformation</strong>.</p><h3>2. Warping VS Alignment</h3><p>Before getting into the topic: how to find the image transformation, let’s first elaborate on what do we have and what do we want to do. For this, we need to know the difference between two tasks, <em>Warping</em> and <em>Alignment</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mjLepKoyObIGLjlS8pYCyg.png" /><figcaption><strong>Figure 3. Definition of Warping and Alignment, from [1, 2]</strong></figcaption></figure><p>Given an image 1 and the image transformation, <em>Warping</em> is what an image 1 would be like after the transformation. On the contrary, <em>Alignment</em> is given two images and seeking for what is the transformation between two images?</p><p>As one might notice, <em>Alignment</em> is the task we want to solve by finding an appropriate transformation <strong><em>T</em></strong>. Then how can we find such <strong><em>T</em></strong>?</p><p>Since the transformation is applied in pixel-wise mannel, we first need to find candidate points. Further, a points from one image should be matched to one point from the other image, and the found pairs are used to determine the transformation <strong><em>T</em></strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tXvbZ-gzDO3jVvwafFufhA.png" /><figcaption><strong>Figure 4. Matrix representation of the task: Finding an image transformation T (in matrix form, M), from [1, 9]</strong></figcaption></figure><p>Fortunately, we already have the interest point pairs from local feature descriptors. <strong>Therefore, what is left is just to find the transformation T (or M, in matrix form).</strong></p><p><strong>But how?</strong></p><h3>3. Types of Transformation</h3><p>There are three models for the transformation, which are Linear, Affine, and Projective transformation. Choosing which model to define the transformation between matching feature pairs is depends on the task we are working on. Although the projective transformation is the commonly selected model in general, we will take a look at each of them, how they are defined and how to find the values for parameters of the transformation matrices.</p><h4>3.1 Linear Transformation</h4><p>Linear transformations are combinations of Scale, Rotation, Shear, and Mirror operations. One property of Linear transform is that only the linear transformations can be represented as <em>2⨯2</em> matrix. Other types of transformation need ‘Homogeneous Coordinate’ to represent them in a matrix form.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SlCHRMijNq1yPuAtNoDroA.png" /><figcaption><strong>Summary of Linear Transformations, adapted from [1]</strong></figcaption></figure><p>In order to fit the parameters of Linear Transformations according to the set of matching feature pairs (also called ‘correspondences’), the well known approach:<strong><em> Least Squares Estimation</em></strong> is applied.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*zMRIKNA8eZpv6RyrkZPSrg.png" /><figcaption><strong>Complete picture of Least Squares Estimation to determine 2D Linear Transformation, adapted from [1]</strong></figcaption></figure><p>Given the set of interest points <strong><em>X</em></strong> and <strong><em>X&#39;</em> </strong>from image 1 and image 2, respectively, the goal is to find a proper linear function to predict <strong><em>X</em></strong> from <strong><em>X&#39; </em></strong>such that<strong><em> aX+b = X&#39;</em></strong>. As we have two unknown parameters, we need two equations to determine the unique solution. Therefore, we need to have at least two matching pairs of interest points.</p><p>However, it is common that we get more pairs than two out of two given images. In this case, we concatenate all pairs and apply pseudo inverse to find a solution (for the parameter <strong><em>a</em></strong> and <strong><em>b</em></strong>) such that it minimizes the squared error.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/714/1*UDKEVLHVzTKhq0YXdtG8DA.png" /><figcaption><strong>Pseudo Inverse to determine the solution for x</strong></figcaption></figure><h4>3.2 Affine Transformation</h4><p>Shortly, Affine transformation is the combination of any linear transformation and ‘<strong><em>translation</em></strong>’. One property to know is that the parallel lines remain parallel after Affine transformations. Further, as Affine transformation for a 2D point cannot be represented by <em>2⨯2</em> matrix, due to the translation part, the Homogeneous coordinate is applied to represent the 2D Affine transformation by 3<em>⨯3</em> matrix as follows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/980/1*sbBAlXHxqCjcn50zI1fPeQ.png" /><figcaption><strong>Translation operation for a 2D point represented in Matrix form</strong></figcaption></figure><p>All linear transformations represented using Homogeneous coordinate are shown below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tT79p2NL8Epjv_2MSBhbMg.png" /></figure><p>Now then how can he find the values for parameters (<strong><em>a, b, c,…, f</em></strong>) of Affine transformation?</p><p>As now we have 6 degree of freedom, we need three pairs of matching interest points to solve and find the unique solution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/888/1*iJU7pmgZJ1cSwZxdYykgpA.png" /></figure><p>In case there are more than the three pairs, <strong><em>Least Squares Estimation </em></strong>can again be applied to find the solution.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/980/1*rH5WOS4ejbCiSVM_mrKP_Q.png" /></figure><h4>3.3 Projective Transformation (Homography)</h4><blockquote>Homography is a mapping between any two perspective projections with the same center of projection, according to [1]. For example, two planes in 3D along the same sight ray.</blockquote><p>The following properties hold in Homography:</p><ul><li>Rectangle should map to an arbitrary quadrilateral.</li><li>Straight lines are preserved.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UYaAR0jaiUK7tlab8xCsSg.png" /><figcaption><strong>Illustrated Projective Transformation, adapted from [1]</strong></figcaption></figure><p>In order to fit a Homography estimating the transformation, we need slightly different approach from the one for previous transformations. Let’s start with the problem definition. Again, we have the matching correspondences, which is noted (A, B) in the following image, and 8 degree of freedom.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1012/1*xR8yAdjcq9oOQuvUQ4RDSA.png" /><figcaption><strong>Two given images with matching pairs of interest points (A, B) from [1, 2]</strong></figcaption></figure><p>The complete process to estimate the transformation matrix is illustrated in the figure below. As now the number of parameters is eight, we need 4 pairs to determine the unique solution. When getting into obtaining the solution that minimizes the least squared error for all found pairs (when number of pairs is larger than 4), one might notice we cannot apply the <em>pseudo inverse </em>approach<em> </em>here, as the rightside of the equation is zero (<strong><em>Ah=0</em></strong>), and therefore we can only obtain a trivial solution with pseudo inverse.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*13ws147uqK4jZ7X5vxMyEw.png" /><figcaption><strong>Figure 5. Derivation of fitting a Homography, adapted from [1, 2]</strong></figcaption></figure><p>Let’s take this equation <em>Ah=0 </em>from different perspective. A is a matrix and h is a vector. Recall the definition of eigenvector and eigenvalue. Then the <em>h</em> of <em>Ah=0 </em>can be interpreted as finding the eigenvector <em>h</em> corresponding to the eigenvalue of zero. While this approach seems nice, one problem remains that the matrix <em>A</em> is likely not to be a square matrix.</p><p><strong>Therefore, we can apply the singular vector decomposition (SVD) instead, and find the singular vector <em>h</em> that corresponds to the singular value of zero.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*M7RZciYUbCAa1racv0aPYg.png" /><figcaption><strong>FIgure 6. Solution to fitting a Homography using SVD, adapted from [1, 2]</strong></figcaption></figure><p>The following figure is the result of stitched two images using the estimated homography.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*smNIBbWOhIRzoZtHm-5Lqg.png" /><figcaption><strong>Figure 7. Example of homography in real images, from [1]</strong></figcaption></figure><p><strong>Before I wrap up this article, one should keep in mind that the homography only holds for planar(flat) surface, such as walls not car, cat.</strong></p><p>More specifically, according to [1], <em>Homography</em> can model</p><ul><li>transformation across images of any scene taken from the exact same camera position (center of projection)</li><li>transformation across images of a planar object taken from any camera position</li></ul><p>These two cases are illustrated in the following.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SOFMxdpTepwljsCtMxWFcA.png" /><figcaption><strong>Figure 8. Examples of two cases when Homography holds, from [12]</strong></figcaption></figure><p>In case you need one for non-planar object, you can consider to use <strong><em>‘Fundamental Matrix’.</em></strong></p><h3>4. RANSAC</h3><p>In order to increase the accuracy and the quality of Image transformation, one can consider to apply RANSAC.</p><blockquote>The content is planned to be updated</blockquote><p>Please refer to <a href="http://www.cse.psu.edu/~rtc12/CSE486/lecture15.pdf">here</a> for more information at the moment.</p><h3>Reference</h3><p>[1] <a href="https://www.vision.rwth-aachen.de/courses/">RWTH Aachen, computer vision group</a></p><p>[2] <a href="http://vision.cs.utexas.edu/376-spring2018/">CS 376: Computer Vision of Prof. <strong>Kristen Grauman</strong></a></p><p>[3] <a href="https://homes.cs.washington.edu/~seitz/"><strong>S. Seitz</strong></a><br>[4] <a href="https://www.amazon.de/Computer-Vision-Approach-David-Forsyth/dp/013608592X"><strong>Forsyth &amp; Ponce</strong></a></p><p>[5] Prof. <a href="https://slazebni.cs.illinois.edu/"><strong>Svetlana Lazebnik</strong></a></p><p>[6] <a href="https://scholar.google.com/citations?user=5hJNWakAAAAJ&amp;hl=en">Prof <strong>M. Irani</strong></a> and <strong>R.</strong> <strong>Basri</strong></p><p>[7]<a href="https://scholar.google.com/citations?user=rDfyQnIAAAAJ&amp;hl=en"> Prof. <strong>Li fei-fei</strong></a></p><p>[8] <a href="https://scholar.google.com/citations?user=jkm1ipUAAAAJ&amp;hl=en">Denis Simakov</a></p><p>[9] <a href="https://scholar.google.com/citations?user=d97bGd8AAAAJ&amp;hl=ko">Alexej Efros</a></p><p>[10] <a href="https://scholar.google.com/citations?user=s1IAWfgAAAAJ&amp;hl=en">Prof. Krystian Mikolajczyk</a></p><p>[11] <a href="https://darkpgmr.tistory.com/79">Homography1</a></p><p>[12] <a href="https://darkpgmr.tistory.com/153?category=460965">Homography2</a></p><p>[13] <a href="http://dept.me.umn.edu/courses/me5286/vision/Notes/2015/ME5286-Lecture8.pdf">Saad J Bedros</a></p><p>[14] <a href="https://docs.opencv.org/master/d9/dab/tutorial_homography.html">OpenCV</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4006f28e103" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[CV] 13. Scale-Invariant Local Feature Extraction(3): SIFT]]></title>
            <link>https://medium.com/jun94-devpblog/cv-13-scale-invariant-local-feature-extraction-3-sift-315b5de72d48?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/315b5de72d48</guid>
            <category><![CDATA[computer-vision]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Wed, 16 Dec 2020 13:23:47 GMT</pubDate>
            <atom:updated>2020-12-16T13:23:47.515Z</atom:updated>
            <content:encoded><![CDATA[<h3>1. SIFT (Scale Invariant Feature Transform)</h3><p>Another scale-invariant algorithm I want to address is the <em>SIFT. </em>With <em>SIFT</em>, the location of local feature points (interest points) are extracted from an image, and further, the corresponding vector representation of the respective interest point is generated, which could be used later on for feature matching between images. As <em>SIFT</em> has quite many steps involved, it might seem complicated and frustrated but many of them are from what we already studied (e.g. feature descriptor like <em>HoG</em>, scale selection for local feature points by <em>LoG</em>).</p><p>We will go through the flow of <em>SIFT</em> one by one, but before getting into the detail of each step, I will first give you the bird’s-eye view of <em>SIFT</em>.</p><p><strong>(1) Scale-space extrema detection</strong></p><ul><li>Similar to Harris-Laplace detector, <em>SIFT</em> searches interest point candidates over all points in the image and scales, and store a list of computed candidates in form of <strong><em>(x, y, </em></strong><em>σ</em><strong><em>). </em></strong>This list will be used for later steps.</li></ul><p><strong>(2) Keypoint localization and filtering</strong></p><ul><li>For each interest point candidate, a detailed model is applied to determine the final location and scale of the candidate. Afterward, thresholding is performed to remove unlikely candidates</li></ul><p><strong>(3) Orientation assignment</strong></p><ul><li>To ensure the rotation invariance, one or more orientations are assigned to each keypoint using the computed image gradient directions. These assigned orientations are later used to match and align the image patches (regions) around interest points.</li></ul><p><strong>(4) Generation of vector representation for interest points</strong></p><ul><li>The local image gradients in the patch (also called window or region) around the key point <strong>at the selected scale</strong> are measured and transformed into a vector representation using a descriptor.</li></ul><h4>Step (1): Scale-space extrema detection</h4><p>The first step of <em>SIFT</em> algorithm is searching keypoints <strong><em>(x, y, </em></strong><em>σ</em><strong><em>) </em></strong>in image over scales. Although the approach of <em>SIFT</em> to find a suitable scale for a point is similar to as Harris-Laplace did, there is a slight modification for cheaper computation.</p><p><strong>Step (1.1): Approximation of <em>LoG </em>by <em>Difference of Gaussian (DoG)</em> in automatic scale selection</strong></p><p>Recall that in the <a href="https://medium.com/jun-devpblog/cv-11-scale-invariant-local-feature-extraction-1-auto-scale-selection-265049027bf1">automatic scale selection</a> where the Laplacian-of-Gaussian (<em>LoG</em>) is chosen as a signature function. A scale σ for a point <strong><em>(x, y)</em></strong> in an image was selected as the suitable scale among other scales, if <strong><em>(x, y, </em>σ<em>) </em></strong>outputs the highest <em>LoG</em> response among 26 points from the same and neighboring scales.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1Kmcz0qJ95axb8q-e6uDKg.png" /><figcaption><strong>Figure 6. Automatic scale selection with Laplacian of Gaussian, adapted from [1, 10]</strong></figcaption></figure><p>One might remember that the <em>LoG</em> filter can be approximated by the <em>Difference-of-Gaussian </em>(<em>DoG</em>) with fewer computations, meaning that we can efficiently approximate the Laplacian by performing two Gaussian-blurring operations with different variance terms <strong>σ</strong> and substracting one Gaussian-blurring result by the other one, as is illustrated in the following figure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2c7knESJASuLL4wjvjbNMg.png" /><figcaption><strong>Figure 7. Comparison of Laplacian-of-Gaussian and Difference-of-Gaussian, adapted from [1]</strong></figcaption></figure><p>In summary, one can consider this process as replacing each layer in the scale space, produced by LoG, with that produced by <em>DoG </em>for the sake of efficient computation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dy6cbo5mi-MrCcKBb0EajA.png" /><figcaption><strong>Figure 8. Applying DoG instead of computing LoG response map in each scale space, adapted from [1]</strong></figcaption></figure><p><strong>Step (1.2): Detecting extreme in the scale space generated by <em>Gaussian Pyramid</em> and <em>DoG</em></strong></p><p>Despite the DoG is a decent approximation of LoG, the quality of approximation depends on the choice of two Gaussian variances, σ and 𝒌σ. In order to improve the approximation quality, <strong>SIFT conducts more than one DoG operations with increasing Gaussian kernel variances σ.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*O931QRggVhf8_C9BKLnWXw.png" /><figcaption><strong>Figure 9. Scale space produced by DoG, from [1, 10]</strong></figcaption></figure><p>However, just doing this does not guarantee that SIFT is scale-invariant because <strong><em>Fig 9 </em>is an approximation of one layer from the scale space produced by LoG, meaning that the algorithm currently only looks at the image in one fixed scale.</strong> In order to observe the image from many different scales, <em>SIFT</em> integrates the idea of <em>Gaussian Pyramid</em> into this.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/738/1*WEt5azLgY66LIk4QSxaenw.png" /><figcaption><strong>Figure 10. Produced Octaves by Gaussian pyramid (sequence of consecutive blurring and sampling), from [13]</strong></figcaption></figure><p><a href="https://medium.com/jun-devpblog/cv-4-multi-scale-representation-gaussian-and-laplacian-pyramid-527ca4c4831c"><em>Gaussian pyramid</em></a> is a multi-scale representation of an image containing a properly re-sized(re-scaled) version of the original image by sampling with Gaussian blurring in order to avoid the aliasing issue. The rescaled results of an image are named as ‘Octave’ in <em>Fig 10</em>.</p><p><strong>Given the octaves from <em>Gaussian pyramid</em>, SIFT conducts the operation in <em>Fig 9</em> with DoG for each octave.</strong> As a result, we obtain the complete ‘scale space (see <em>Fig 11</em>)’ which approximates that generated by <em>LoG</em> in <em>Fig 6</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*kH4O4fwqjC-ZRTmCUp550w.png" /><figcaption><strong>Figure 11. Approximated scale space by Gaussian pyramid and DoG, adapted from [1, 10]</strong></figcaption></figure><p><strong>Step (1.3): Local extreme detection</strong></p><p>Given the scale space in <em>Fig 11</em>, local extrema (either maxima or minima) are detected by comparing a pixel (<em>red circle</em>) to its 26 neighbors (<em>green</em>) in <em>3×3</em> window at the current and adjacent (above and below) scales. More specifically, only a point <em>DoG</em><strong><em>(x, y, </em></strong><em>σ</em><strong><em>)</em></strong> is selected if it is larger or smaller than all of its neighbors. The list of detected extremum <strong><em>(x, y, </em></strong><em>σ</em><strong><em>)</em></strong> is the<strong> keypoint candidates</strong> which will be processed later on in <em>SIFT</em> algorithm.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/996/1*l749fH78tLf6KNKGsmVnng.png" /><figcaption><strong>Figure 12. Local extrema detection, from [13]</strong></figcaption></figure><h4>Step (2): <strong>Keypoint localization and filtering</strong></h4><p>After finding keypoint candidates by comparing a pixel with its adjacent pixels, the next step is to fit them in a detailed model to more accurately localize the keypoints and filter unlikely keypoints out from the candidate list.</p><p>The detailed ‘model’ I referred to is a 3D quadratic scale-space function using the <em>Taylor expansion</em>, which is proposed by Brown and Lowe at 2002, for localization, and <em>2×2 Hessian matrix</em> for filtering.</p><p><strong>Step (2.1): Keypoint localization with <em>Taylor expansion</em></strong></p><p>Let’s mark the detected extrema from step (1) as blue in <em>Fig 13, </em>where the true function and extrema are illustrated<em>. </em>As the scale space produced in <em>step 1</em> is the discretized version of true-continuous scale space. Therefore, it is not guaranteed that the detected extrema in discrete scale space are the true extrema.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2OuKwiParkZrpW6Ci6xYzw.png" /><figcaption><strong>Figure 13. Visualization of why the keypoint localization is needed, from [14]</strong></figcaption></figure><p>To solve this and find the location of <strong>TRUE</strong> extremum, the Taylor expansion is used to get the 3D quadratic approximation of the scale-space function, <strong><em>D</em></strong><em>(x, y, σ)</em>. Afterward, by computing its derivative with respect to x, and finding the point where it goes to zero, give us the location of <strong>true</strong> <strong>extremum</strong>. Mathematically, this process can be represented as follows.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WagqtdWA0BpsGWurbDjSAA.png" /></figure><blockquote>Note that, here, the expansion is only up to the quadratic terms.</blockquote><p><strong>Step (2.2): Filtering</strong></p><p>For stability and computational efficiency, SIFT applies two filtering operations. The first one is removing the detected extrema from 2.1 whose absolute value is less than a certain threshold (in the paper, <em>0.03</em>). This makes sense because extremum with a low value indicates the extremum has a low contrast to its neighboring points, and therefore, such extremum is unstable and is not important as a local feature.</p><p>The second one is eliminating extreme which came from edges. Since the Difference-of-Gaussian, which has a strong response along edges, is used while constructing the scale space, some of the detected extrema are located on an edge even though the edge is poorly determined. Since these extreme makes SIFT instable, the <em>2×2 Hessian matrix, </em><strong><em>H, </em></strong>is computed at the location and scale of keypoint (extremum).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/324/1*BCKxFzOaFGbshOGWuETviQ.png" /></figure><p>Then using the eigenvalues, 𝛂 and 𝜷, of <strong><em>H</em></strong>, it determines whether one eigenvalue is significantly smaller than the other one or not. Recall how the Harris detector detects the edge. If both eigenvalues are large then the point is a corner, and if one is noticeably smaller than the other then it means the point is on an edge.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*S73dtEgwmyBcSPS1ynmmJA.png" /><figcaption>Figure 14. Classification of image points using eigenvalues, from [1, 2]</figcaption></figure><p>With this idea, SIFT checks all keypoints and tells whether each one of them is a suitable keypoint to be considered as a local feature or not.</p><blockquote>As I only describe the intuition, not the complete detail, please visit <a href="https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf">here</a> for more information.</blockquote><p>After filtering, the number of candidates decreases and only strong and likely keypoints survive. The following figure presents the selected keypoints from each stage of the described steps above.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JR08P3XEMK2YlfyizKt-JA.png" /><figcaption><strong>Figure 15. keypoint selection. (a) Given image. (b) 832 keypoints location at extreme(maxima and minima) of DoG function in scale space. (c) After removing extreme with low contrast, 729 keypoints survive. (d) After eliminating edge responses, 536 keypoints remain. from [15]</strong></figcaption></figure><h4>Step (3): <strong>Orientation assignment</strong></h4><p>After <em>step (2)</em>, a set of good point (<em>x, y, σ</em>) is obtained. <em>σ </em>tells at which <em>Gaussian-blurred image</em> and at which octave in the <em>Gaussian pyramid</em> the extrimum<em> </em>(<em>x, y) </em>is computed<em>. </em>In other words, we can represent the Gaussian-blurred image<em> </em><strong><em>L</em></strong><em> </em>from which the extrimum<em> (x, y, σ)</em> is computed as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/534/1*HQrU9j9IyXlfmaBwjMeZFQ.png" /></figure><p>Then for all sample point in the image <strong><em>L</em></strong>, the gradient magnitude, <strong><em>m,</em></strong> and the orientation, <strong><em>θ,</em></strong> are precomputed using the pixel differences.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pEZiuujLDlPKCwwR2t7SSw.png" /></figure><p>Subsquently, 16<em>×16</em> region (window) around the keypoint is taken, and an orientation histogram is formed. The histogram has 36 bins where each bin covers 10 degrees so that the 360 degree range of orientations are covered. Note that when filling each orientation bin by the gradient magnitude m, the magnitude is weighted by the 2D Gaussian filter whose σ is 1.5 times that of the scale of the keypoint.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1010/1*hnN3Z1ZZXMpf43nqt91y3Q.png" /><figcaption><strong>Figure 16. Weighted gradient magnitude map by Gaussian kernel which is to be fed into the orientation histogram</strong></figcaption></figure><p>Lastly, we need to find the dominant gradient orientation of the region by looking up the highest peak in the histogram. The detected dominant orientation is, then, assigned to the keypoint, and <em>SIFT</em> repeats this orientation assignment process for all keypoints in the set. <strong>Therefore, each keypoint has, now, 4 entries: location coordinates, scale, and the assigned orientation</strong> <em>(x, y, σ, θ).</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*LYpnMuXsYxxBu9apbpsC6g.png" /><figcaption><strong>Figure 17. Example of detecting the dominant orientation from 8 x 8 region, from [14]</strong></figcaption></figure><p>The orientation assigned to a keypoint will be used in the next step to ensure the rotation invariance of <em>SIFT and </em>when matching keypoints from different images.</p><blockquote>If the way of constructing the orientation histogram is not familiar, please read <a href="https://medium.com/jun-devpblog/cv-9-object-detection-with-sliding-window-and-feature-extraction-hog-cf1820c86b46">this</a> or google the keyword ‘HoG: Histogram of gradient’.</blockquote><h4>Step (4): Generation of vector representation for interest points</h4><p>By previous operations, an image location<em> (x, y)</em>, scale <em>σ, </em>and orientation <em>θ </em>are assigned to each detected keypoint. As the last step, a local descriptor is computed for a local region around each key point in a similar way to step (3), using the histogram of gradient.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WCFIwODh3BFOMbnbUtnFZw.png" /><figcaption>Figure 18. Local keypoint descriptor of SIFT</figcaption></figure><p>One difference from the histogram of gradient, which is computed in the orientation assignment process in<em> step (3)</em>, is that the 16 <em>×</em>16 region around a keypoint is sub-divided into 16 cells of the size 4<em>×4. </em>The rest parts are the same as <em>step (3)</em>. The histogram of gradient is computed for each cell with 8 orientation bins, which are filled by Gaussian-kernel-weighted magnitudes.</p><p>Then, a total of 16 histograms from the cells are concatenated to produce the final vector representation of a local keypoint. <strong>The generated vector has a length of <em>16️️*8 (the number of cells * the number of histogram bins).</em></strong></p><p>We are almost there to the end, but there is one operation left. By using <em>Gaussian pyramid and DoG</em>, the local feature descriptors generated by <em>SIFT</em> become scale-invariant. The rotation invariance, however, which is also important, has not yet been achieved.</p><p>To ensure the rotation invariance to <em>SIFT</em>, each region around a keypoint (on which the histogram of local gradients is computed) <strong>is rotated relative to the <em>assigned keypoint orientation from step (3)</em></strong> so that the dominant orientation points upwards.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qhHkVsPO4vC51YPSqqBfWw.png" /></figure><p>By doing this, all local descriptors have the same dominant orientation, and therefore, while computing the similarity between descriptors, <em>SIFT</em> can make an accurate and rotation-invariant comparison.</p><h4><strong>This is the end of the flow of SIFT.</strong></h4><p>In summary, by far we have taken a look at how to extract local features and build descriptors for them in a scale and rotation-invariant manner with <em>Harris-Laplace</em> and <em>SIFT</em>. The computed local descriptor for a keypoint is to be compared with that of another keypoint while feature mapping to determine whether the two keypoints from two different images are the same or not.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hhaE9SzB7bn0DWPFKpOltQ.png" /><figcaption>Figure 18. The usage of computed local feature descriptors for feature mapping, adapted from [1]</figcaption></figure><p>It can be done by measuring the similarity between two descriptors, and it gives us the matched keypoint pairs from two images.</p><p>One computer vision task, which can be solved by making use of the pairs, is <em>image stitching</em>, meaning how can we properly align or combine two images of the same object, but taken from a different angle, or perspective.</p><p>In the next article, I will address how to approach the image stitching using the extract local features.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ot959cvObEPyG3bD2w6tkw.png" /><figcaption><strong>Appendix. Scale space construction with Gaussian pyramid and DoG</strong></figcaption></figure><h3>Reference</h3><p>[1] <a href="https://www.vision.rwth-aachen.de/courses/">RWTH Aachen, computer vision group</a></p><p>[2] <a href="http://vision.cs.utexas.edu/376-spring2018/">CS 376: Computer Vision of Prof. <strong>Kristen Grauman</strong></a></p><p>[3] <a href="https://homes.cs.washington.edu/~seitz/"><strong>S. Seitz</strong></a><br>[4] <a href="https://www.amazon.de/Computer-Vision-Approach-David-Forsyth/dp/013608592X"><strong>Forsyth &amp; Ponce</strong></a></p><p>[5] Prof. <a href="https://slazebni.cs.illinois.edu/"><strong>Svetlana Lazebnik</strong></a></p><p>[6] <a href="https://scholar.google.com/citations?user=5hJNWakAAAAJ&amp;hl=en">Prof <strong>M. Irani</strong></a> and <strong>R.</strong> <strong>Basri</strong></p><p>[7]<a href="https://scholar.google.com/citations?user=rDfyQnIAAAAJ&amp;hl=en"> Prof. <strong>Li fei-fei</strong></a></p><p>[8] <a href="https://scholar.google.com/citations?user=jkm1ipUAAAAJ&amp;hl=en">Denis Simakov</a></p><p>[9] <a href="https://scholar.google.com/citations?user=d97bGd8AAAAJ&amp;hl=ko">Alexej Efros</a></p><p>[10] <a href="https://scholar.google.com/citations?user=s1IAWfgAAAAJ&amp;hl=en">Prof. Krystian Mikolajczyk</a></p><p><a href="https://medium.com/data-breach/introduction-to-sift-scale-invariant-feature-transform-65d7f3a72d40">[11] SIFT</a></p><p>[12] <a href="http://dept.me.umn.edu/courses/me5286/vision/Notes/2015/ME5286-Lecture8.pdf">Saad J Bedros</a></p><p>[13] <a href="https://ballentain.tistory.com/47">SIFT2</a></p><p>[14] <a href="https://www5.cs.fau.de/fileadmin/lectures/2011s/Lecture.2011s.CV/sift.pdf">Prof. Elli Angelopoulou</a></p><p>[15] <a href="https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf">Sift paper</a></p><p><strong>Any corrections, suggestions, and comments are welcome</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=315b5de72d48" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jun94-devpblog/cv-13-scale-invariant-local-feature-extraction-3-sift-315b5de72d48">[CV] 13. Scale-Invariant Local Feature Extraction(3): SIFT</a> was originally published in <a href="https://medium.com/jun94-devpblog">Learning</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[CV] 12. Scale-Invariant Local Feature Extraction(2): Harris-Laplace]]></title>
            <link>https://medium.com/jun94-devpblog/cv-12-scale-invariant-local-feature-extraction-2-harris-laplace-170d48ee1bf1?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/170d48ee1bf1</guid>
            <category><![CDATA[computer-vision]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Tue, 15 Dec 2020 17:07:52 GMT</pubDate>
            <atom:updated>2020-12-15T17:07:52.751Z</atom:updated>
            <content:encoded><![CDATA[<blockquote>This article is the second part of the topic: scale-invariant local feature extraction. As I assume you know local feature detectors (Harris, Hessian), feature descriptors (HoG), and automatic scale selection (with LoG) by now, please visit here if you have not read the first part yet or not familiar with them before continuing to go over this article.</blockquote><h3>1. Recap</h3><p><em>Harris</em> and <em>Hessian</em> are shophisticatelly designed local feature detectors, which are used to find corners in the image. Despite they show significant performance, one huge limitation lie in them: the Harris and Hessian corner detectors are not invariant to scale.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wfgQ600MfwD36lb7u-ka8g.png" /><figcaption><strong>Figure 1. Why Harris and Hessian corner detectors are not scale-invariant, from [2]</strong></figcaption></figure><p>We also took a look at the automatic scale selection which, as its name implies, finds the most suitable scale for a point <em>(x, y)</em> in an image to be an interest point candidate.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SudDTdJHBGlSZ7Xgu6VBhA.png" /><figcaption>Figure 2. Complete picture of auto scale selection, adapted from [1, 2]</figcaption></figure><p>It uses <em>Laplacian-of-Gaussian</em> as the signature function and detects the location of <em>blobs </em>with its corresponding scale, which returns the highest response, in the image.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hUQmW-wDo8a_Q5IOCYSOjw.png" /><figcaption>Figure 3. Production of the list of Interest point candidates with LoG, adapted from [1, 10]</figcaption></figure><h3>2. Harris-Laplace Detector</h3><p>In order to overcome the limitation of <em>Harris</em> detector and make it robust to the scale changes, the Harris-Laplace detector is designed. As one can image from its name, the <em>Harris-Laplace </em>detectors integrates the automatic scale selection with <em>LoG</em> into the <em>Harris</em> detector. Therefore, it could detect corners regardless of the image scale, meaning that a corner in an image will be constantly detected after resizing the image.</p><p>Let’s take a look how the Harris and LoG are combined for achieving the scale invariance.</p><h4>2.1 Why Harris-Laplace detector is scale-invariant?</h4><p>In short, <em>Harris-Laplace</em> detector is a multi-scaled version of <em>Harris</em> detector where the Harris response is computed repeatedly on the same images but convolved with <em>LoG</em> filters from varying scales 𝝈. <em>Fig 4</em> illustrates this process.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IOZmsYEu-7GNTHIqi3dWLQ.png" /><figcaption><strong>FIgure 4. Visualization of Harris-Laplace detector, from [12]</strong></figcaption></figure><p>The above figure of <em>Harris-Laplace</em> can be summarized as two-step process.</p><ul><li><strong>Step 1.</strong> The <em>Harris-Laplace</em> detector computes interest points at multiple scales using the <em>Harris</em> detector. Let’s say there is a <em>3×3</em> window. Then, at each scale, a point, which outputs the largest <em>Harris</em> response, is chosen as interest point among all points inside the window. After computing the interest point (local maxima in the window), the window is shifted to the next point and repeat this until it goes over the whole image in each scale.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HFv6ckxV6decvko9VO_Z_Q.png" /></figure><blockquote>But note that, as in Harris-Laplace, the second-moment matrix is computed by convolving with Laplacian-of-Gaussian (LoG) filter, not with Gaussian filter, the second-moent matrix <strong>M</strong> and the response function <strong>R</strong> should be revised accordingly, as is shown below.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pQJZmCJIaLx2vgJ5LfDzJA.png" /></figure><ul><li><strong>Step 2. </strong>Given the list of interest points from different scales 𝝈, Harris-Laplace detector searches interest points in the list such that they are not only the local maxima in their respective scale, but also in their neighboring scales. In other words, a interest point from step 1 is again compared with 18 points from adjacent scales (9 points from each scale) whether it is maximal or not.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WECCXGISHG8DTekMe4Ed5g.png" /></figure><p>After <em>step 2</em>, the remaining interest points are the final detection results. They are visualized as circle where the center of circle indicates the position of interest point and the radius implies the scale where it come from.</p><p>In conclusion, the <em>Harris-Laplace </em>is a scale-invariant detector as it searchs local features (corners) over the scale space.</p><p>The following<em> Fig 4</em> is the result of three pairs of input image from <em>Harris-Laplace</em>. One image in a pair is rotated and scaled version of the other one. As we can observe, regardless of the shift in scale and view point, the <em>Harris-Laplace</em> detector locates the same local features from images.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*H5yMkViA4XnLfT2hvLCpzQ.png" /><figcaption><strong>Figure 5. Harris-Laplace detection results, from [10]</strong></figcaption></figure><h3>3. Reference</h3><p>[1] <a href="https://www.vision.rwth-aachen.de/courses/">RWTH Aachen, computer vision group</a></p><p>[2] <a href="http://vision.cs.utexas.edu/376-spring2018/">CS 376: Computer Vision of Prof. <strong>Kristen Grauman</strong></a></p><p>[3] <a href="https://homes.cs.washington.edu/~seitz/"><strong>S. Seitz</strong></a><br>[4] <a href="https://www.amazon.de/Computer-Vision-Approach-David-Forsyth/dp/013608592X"><strong>Forsyth &amp; Ponce</strong></a></p><p>[5] Prof. <a href="https://slazebni.cs.illinois.edu/"><strong>Svetlana Lazebnik</strong></a></p><p>[6] <a href="https://scholar.google.com/citations?user=5hJNWakAAAAJ&amp;hl=en">Prof <strong>M. Irani</strong></a> and <strong>R.</strong> <strong>Basri</strong></p><p>[7]<a href="https://scholar.google.com/citations?user=rDfyQnIAAAAJ&amp;hl=en"> Prof. <strong>Li fei-fei</strong></a></p><p>[8] <a href="https://scholar.google.com/citations?user=jkm1ipUAAAAJ&amp;hl=en">Denis Simakov</a></p><p>[9] <a href="https://scholar.google.com/citations?user=d97bGd8AAAAJ&amp;hl=ko">Alexej Efros</a></p><p>[10] <a href="https://scholar.google.com/citations?user=s1IAWfgAAAAJ&amp;hl=en">Prof. Krystian Mikolajczyk</a></p><p><a href="https://medium.com/data-breach/introduction-to-sift-scale-invariant-feature-transform-65d7f3a72d40">[11] SIFT</a></p><p>[12] <a href="http://dept.me.umn.edu/courses/me5286/vision/Notes/2015/ME5286-Lecture8.pdf">Saad J Bedros</a></p><p>[13] <a href="https://ballentain.tistory.com/47">SIFT2</a></p><p><strong>Any corrections, suggestions, and comments are welcome</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=170d48ee1bf1" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jun94-devpblog/cv-12-scale-invariant-local-feature-extraction-2-harris-laplace-170d48ee1bf1">[CV] 12. Scale-Invariant Local Feature Extraction(2): Harris-Laplace</a> was originally published in <a href="https://medium.com/jun94-devpblog">Learning</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[CV] 11. Scale-Invariant Local Feature Extraction(1): Auto Scale Selection]]></title>
            <link>https://medium.com/jun94-devpblog/cv-11-scale-invariant-local-feature-extraction-1-auto-scale-selection-265049027bf1?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/265049027bf1</guid>
            <category><![CDATA[computer-vision]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Sun, 13 Dec 2020 23:30:19 GMT</pubDate>
            <atom:updated>2020-12-15T13:54:19.310Z</atom:updated>
            <content:encoded><![CDATA[<h3>1. Motivation: Why scale-invariant?</h3><p>Let’s recall what we studied about the local feature extractors: Harris and Hessian in <a href="https://medium.com/jun-devpblog/cv-10-local-feature-descriptors-harris-and-hessian-corner-detector-7d524888abfd">the last article</a>. Harris and Hessian are strong corner detectors. However, detectors are rotation invariant. However, they are not scale-invariant, which is a crucial drawback in terms of feature detection. The reason why scale invariance is important is intuitively visualized in the following figure slide from <a href="http://vision.cs.utexas.edu/376-spring2018/">[2]</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*ikFB6TqoZ_L5Pm0g.png" /><figcaption>Figure 1. Why the scale invariance is important, from [2]</figcaption></figure><p>Let’s say we have two same images but with different scales (one is an upsampled version of the other one) as is shown above. When the image is in a suitable scale for the detection window to contain the corner in it, the Harris and Hessian detectors can find the corner (left panel).</p><p>How about the case when the image is upscaled, and therefore, the corner is accordingly magnified so that the corner has a larger size than the detection window?</p><p>As is illustrated in the right panel of Figure 1, what detection windows of the detector perceive becomes an edge, not a corner. Therefore, the detectors cannot find the corner which was able to be detected before the scale change.</p><p>In short, A corner in an image being detected by mentioned local-feature detectors (<em>Harris and Hessian</em>) depends on the scale. And for sure, this is not desirable. We want the detectors to be able to detect corners in an image regardless of the scale. <strong>Thus, this article will address some approaches to build detectors, which find corners in a scale-invariant manner.</strong></p><h3>2. Fundamentals to Scale-Invariant Detectors.</h3><p>Before getting into the detail of scale invariance, there are two conceptions that should be preceded.</p><h4>2.1 From point to region</h4><p>The <em>Harris</em> and <em>Hessian</em> operators return us the interest points (𝒙, <strong>𝑦) </strong>where corners are located. However, in order to define the feature descriptions (feature vector representations) for the interest points, and to compare the points between images, we need more than just a point of interest, but a region around it.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bZ0CltC5Cn6FRR58Dpxw3A.png" /><figcaption><strong>Figure 2. Detected point of interest and its corresponding defined region</strong></figcaption></figure><p>Think of the <em>HoG</em> feature descriptor. It computes the histograms of gradient and constructs a feature representation for pixels in the given image patch (region).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*j0coIQmGNrV_tbrmoAisvQ.png" /><figcaption>Figure 3. Comparison of two feature representations extracted from regions of different images, from [1, 10]</figcaption></figure><p><strong>The simplest way to define a region is to take <em>16 ⨯ 16</em> pixels around the detected point.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/594/1*dgANZvIgWmggtNxn8N18aA.png" /><figcaption>Figure 4. Example of a region defined around the point of interest (keypoint), from [11]</figcaption></figure><h4>2.2 Scale selection</h4><p>By using feature representations extracted from regions around the interest points, we can compare and measure how similar the two image regions are to each other.</p><p>Now the question is, considering the fact that Harris and Hessian are not scale-invariant,<strong> how to choose the correct scale for respective regions around interest points?</strong></p><p><strong>2.2.1 Exhaustive search</strong></p><p>One naive approach is to compare a feature representation of point <strong><em>A</em></strong> from one scale to another feature representation of point <strong><em>B</em></strong> for each region around <strong><em>B</em></strong> from all possible scales. This way is called ‘Exhaustive search’ since is computationally inefficient, but still possible for matching.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1CgbgoRH-1aYpfLq0_WOUw.png" /><figcaption><strong>Figure 4. Illustration of the exhaustive search, from [1, 10]</strong></figcaption></figure><p><strong>2.2.2 Automatic scale selection</strong></p><p>Another approach to the optimal scale selection is to design a <em>signature function</em> on the region (image patch around the interest point) that is scale-invariant. More specifically, a designed function takes a region around the point and outputs its response as a scalar given the region. Keep in mind that the varying input of this <em>signature function</em> is not the point <strong><em>(x,y)</em></strong>, but the size of the region around the point <strong><em>(x,y)</em></strong>. Therefore, we can consider the signature function as a function of region size (or image patch width) for a point in one image.</p><p>The described definition of <em>signature function </em>might sound not clear. To clarify, the behavior of <em>signature function</em> <strong><em>f</em></strong> with different region sizes of an interest point is illustrated below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZlDPp83Dy5K1T_oSpTyJ7w.png" /><figcaption><strong>Figure 5. Signature function with varying region sizes of an interest point, adapted from [1, 2]</strong></figcaption></figure><p>In <em>Fig 5</em>, we can observe that the function outputs different response values depends on the region size. And more importantly, <strong>the local maxima of this function is a strong clue indicating that the region size corresponding to the local maxima should be invariant to image scale.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hGLRvNdjFdexynuz8CBwrw.png" /></figure><blockquote><em>Note that the </em>signature function<em> we are talking here is not the</em> Harris and Hessian response function<em>! They are different.</em></blockquote><p>The following sequence of images in <em>Fig 6</em> is the visualized process of automatic scale selection given two images (same object but from a different angle, scale, etc.), adapted from [1, 2].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5-u71a9n1-E93tV2WhqfIg.png" /><figcaption><strong>Figure 6. Complete picture of auto scale selection, adapted from [1, 2]</strong></figcaption></figure><p>In this section <em>2.2.2,</em> we have seen how the optimal scale for an interest point is selected. However, one major question remains unanswered:</p><p><strong>Which function can be the signature function used here?</strong></p><h3>3. Choice for signature function: Laplacian-of-Gaussian</h3><p>The popular choice is the Laplacian-of-Gaussian (LoG).</p><blockquote>If LoG does not ring any bell, please find more detail in <a href="https://medium.com/jun-devpblog/cv-3-gradient-and-laplacian-filter-difference-of-gaussians-dog-7c22e4a9d6cc">here</a>, or google it.</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pEbxpmbEe1NGKLJThdWmRw.png" /><figcaption><strong>Figure 7. equation of Laplacian of Gaussian (LoG) and its behavior with circles of increasing scale, adapted from [1]</strong></figcaption></figure><p>Due to the characteristic of <em>LoG</em>, it detects ‘<strong>blobs</strong>’ in the input image and returns the highest response around them. To understand why this is the case, think of the nature of filters. Filters have a shape of what they are designed to detect, and they output the maximum response when the input has the same looking as the filters. Around the center of <em>LoG</em> filter, we can find a blob, and this is why <em>LoG</em> is a blob detector.</p><p><strong>In short, now we are looking for blobs in the image as a local feature and their corresponding suitable scales by applying LoG filters with varying scales 𝝈, as is illustrated in <em>Fig 8</em>.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HZjqpKUelnOJktzGM1muCQ.png" /><figcaption><strong>Figure 8. Automatic scale selection with Laplacian of Gaussian, from [1, 10]</strong></figcaption></figure><p>One thing to keep in mind from <em>Fig 8 </em>is that unlike <em>Fig 5,</em> where the point with the scale corresponding to the global maxima is selected as a interest point, here, a point <strong><em>(x, y)</em></strong> in image is considered as a candidate of interest point if it is local maxima among adjacent pixels in the same and neighboring scales (8 pixels from the same scale space and 18 from neighboring scale spaces).</p><p>Of course, this leads to a larger number of candidates, and therefore, some sort of thresholding is applied to remove unlikely candidates and to reduce computation.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/948/1*fO_7MTDFtZSuhNeYU1Hjmg.png" /><figcaption><strong>Figure 9. LoG detector result, from [1, 5]</strong></figcaption></figure><p>The above figure is a local feature detection result using LoG as a detector and as a signature function for automatic scale selection. Each center of the red circle indicates the position of interest point <strong><em>(x, y)</em></strong>, and the radius implies the corresponding scale detected from <em>Fig 8. </em>This means the interest points from a larger scale space have a larger radius.</p><blockquote><strong>So far, we have taken a look at how to detect local features and how to find suitable scales (region size) for detected local feature points. In the next article, we will take a look at how to make a feature representation by making use of detected local feature points and scales.</strong></blockquote><h3>Reference</h3><p>[1] <a href="https://www.vision.rwth-aachen.de/courses/">RWTH Aachen, computer vision group</a></p><p>[2] <a href="http://vision.cs.utexas.edu/376-spring2018/">CS 376: Computer Vision of Prof. <strong>Kristen Grauman</strong></a></p><p>[3] <a href="https://homes.cs.washington.edu/~seitz/"><strong>S. Seitz</strong></a><br>[4] <a href="https://www.amazon.de/Computer-Vision-Approach-David-Forsyth/dp/013608592X"><strong>Forsyth &amp; Ponce</strong></a></p><p>[5] Prof. <a href="https://slazebni.cs.illinois.edu/"><strong>Svetlana Lazebnik</strong></a></p><p>[6] <a href="https://scholar.google.com/citations?user=5hJNWakAAAAJ&amp;hl=en">Prof <strong>M. Irani</strong></a> and <strong>R.</strong> <strong>Basri</strong></p><p>[7]<a href="https://scholar.google.com/citations?user=rDfyQnIAAAAJ&amp;hl=en"> Prof. <strong>Li fei-fei</strong></a></p><p>[8] <a href="https://scholar.google.com/citations?user=jkm1ipUAAAAJ&amp;hl=en">Denis Simakov</a></p><p>[9] <a href="https://scholar.google.com/citations?user=d97bGd8AAAAJ&amp;hl=ko">Alexej Efros</a></p><p>[10] <a href="https://scholar.google.com/citations?user=s1IAWfgAAAAJ&amp;hl=en">Prof. Krystian Mikolajczyk</a></p><p><a href="https://medium.com/data-breach/introduction-to-sift-scale-invariant-feature-transform-65d7f3a72d40">[11] SIFT</a></p><p><strong>Any corrections, suggestions, and comments are welcome</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=265049027bf1" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jun94-devpblog/cv-11-scale-invariant-local-feature-extraction-1-auto-scale-selection-265049027bf1">[CV] 11. Scale-Invariant Local Feature Extraction(1): Auto Scale Selection</a> was originally published in <a href="https://medium.com/jun94-devpblog">Learning</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[CV] 10. Local Feature Descriptors: Harris and Hessian Corner Detector]]></title>
            <link>https://medium.com/jun94-devpblog/cv-10-local-feature-descriptors-harris-and-hessian-corner-detector-7d524888abfd?source=rss-df1069eeeb53------2</link>
            <guid isPermaLink="false">https://medium.com/p/7d524888abfd</guid>
            <category><![CDATA[computer-vision]]></category>
            <dc:creator><![CDATA[Awaits]]></dc:creator>
            <pubDate>Tue, 08 Dec 2020 15:17:15 GMT</pubDate>
            <atom:updated>2020-12-13T09:42:53.707Z</atom:updated>
            <content:encoded><![CDATA[<h3>1. Motivation</h3><h4>1.1 Why do we need to find local features?</h4><p>In the last <a href="https://lhj940825.medium.com/cv-9-object-detection-with-sliding-window-and-feature-extraction-hog-cf1820c86b46">article</a>, we extracted global features that represent a given image patch in order to detect objects within it. While the global feature representations do nicely their jobs, they also have some major limitations to certain situations, such as occlusions, intra-category variations, and articulations.</p><p>An alternative way is to extract (describe) and match only local regions, which brings the increased robustness for the mentioned situations.</p><p><em>Fig 1</em> shows the difference between global and local feature extraction approaches.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mkjgMQJuu_v72Bx4Zr6HIA.png" /><figcaption><strong>Figure 1. Global (left) vs Local (right) feature representations, from </strong><a href="https://www.researchgate.net/figure/Global-and-local-image-features-representation_fig2_292995470"><strong>here</strong></a></figcaption></figure><p>While the global feature representations are built on taking a whole image (or image patch) as an input, the local feature representations are made for each local region within the image (or patch).</p><h4>1.2 Application of local features</h4><p><strong>(1) Image matching</strong></p><p>Local features are useful when it comes to performing the image matching tasks. Let’s say we have two images taken by two tourists. How do we ensure that these two pictures are from the same tourist spot?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7V7PjrcBg6plYh0YI4F1cg.png" /><figcaption><strong>Figure 2. Pictures from two different view points and filters, taken by two tourists, from [1,3]</strong></figcaption></figure><p>To answer the question, one can extract local features from the pictures, and compare them. If their similarity is higher than a certain threshold, the two pictures are taken from the same tourist spot.</p><p><strong>(2) Image stitching</strong></p><p>Another application of local feature representations is Image stitching. Think of two images, which are of the same object but from different angles, that we want to combine them properly so that they become a one picture.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OOKNrXNRXjLkO6HD6HWWnw.png" /><figcaption><strong>Figure 3. Image stitching example (1), from [1, 8]</strong></figcaption></figure><p><em>Fig 3 </em>is showing two images of a mountain and the task is to stitch them. To do this, we can begin with</p><ul><li>detecting feature points in both images, which are noted as white dots in the following figure.</li><li>Then to find corresponding pairs of detected feature points. (upper panel of <em>Fig 4</em>)</li><li>lastly, use the found pairs in order to align the images so that we obtain the final stitched image. (lower panel of <em>Fig 4</em>)</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hMhwKs_UcBRBrs7Fv0ly4Q.png" /><figcaption><strong>Figure 4. Image stitching example (2), from [1, 8]</strong></figcaption></figure><blockquote>I briefly introduced how the local features can be used to solve mentioned two tasks. Now let’s get into the details.</blockquote><h3>2. Overview of Local Feature Matching</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JnNg4l3_PII-dMz7AAZ_Ew.png" /><figcaption><strong>Figure 5. Illustration of local feature matching, from [1]</strong></figcaption></figure><p>The general approach for both applications: image matching and stitching, with local feature representations, can be summarized as following steps with <em>Fig 5</em>:</p><p>(1) Find distinctive key points from given images.</p><p>(2) <strong>Define a local region around each keypoint.</strong></p><p>(3) Extract and normalize the region content.</p><p>(4) Compute a local descriptor for each normalized region using pixel information (i.e. gradient orientation, magnitude).</p><p>(5) Match the local descriptors between images.</p><blockquote>Note that the reason why we need to define a <strong>region</strong> around each keypoint is that we cannot generate a feature representation from just a single-pixel keypoint. Instead, we need a set of pixels (region) around key point to produce feature representation out of the region (think of how we define feature descriptors, e.g. HoG).</blockquote><blockquote>If this is not clear, please read the <a href="https://lhj940825.medium.com/cv-9-object-detection-with-sliding-window-and-feature-extraction-hog-cf1820c86b46#4269-3bd526dd07cf">previous article</a> regarding how feature representations are built using pixels within an image patch.</blockquote><h4>2.1 Common problems</h4><p>The defined local feature descriptors have two requirements to meet in order to successfully do their job.</p><ul><li>The descriptor should detect the same keypoint independently in both images</li><li>For each point from one image, the descriptor should produce a reliable feature representation to find its corresponding key point in the other image.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5uXP6hb95JJluETQezb-fg.png" /></figure><p>If there is no keypoint pair found, then matching and stitching are impossible.</p><h4>2.2 Keypoint candidates</h4><p>The keypoints we are looking for should have the following properties:</p><ul><li>should be repeatably detected</li><li>should be precisely localized</li><li>should contain interesting contents</li></ul><p>There are some types of keypoint that include the mentioned properties, such as blobs and corners. Among them, this article will address two detectors that are very specific to find <strong>corners</strong>.</p><p>The main idea behind detecting corners as key points is that the region around a corner has two (or more) dominant gradient directions, and they can be used as a repeatable and distinctive feature that represents the region.</p><h4>2.3 Why corners as distinctive interest points?</h4><p><em>Fig 6</em> shows three types of the region we can generally observe from images.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CCUCxtSCUdob70XMEE8Rwg.png" /><figcaption><strong>Figure 6. Illustration of three regions: flat, edge, and corner, from [9]</strong></figcaption></figure><p>From the localization perspective, a key point should be distinctive from the other points in the regions around it, and the corner is the most suitable type of region for this purpose, where the unique key point can be found compared to the other two regions.</p><p>Let’s elaborate on this with an example in <em>Fig 6</em>. The windows in each panel indicate where our detector is currently looking at. Firstly, in the <strong><em>flat</em></strong> regions, regardless of the direction we move the window, the gradient magnitude and orientation of pixels in the window does not change. This means there is no distinctive key point (pixels) in this region as they are all the same.</p><p>Secondly, in the <strong><em>edge</em></strong> regions, moving the window along the edge does not make any change in pixel gradients. Shifting the window in the direction of the pixel gradient, however, makes a change. Nevertheless, It is not sufficiently strong.</p><p>Lastly, the <strong><em>corner</em></strong>, unlike the previous two types of region, yields a significant change in gradient magnitude and orientation when the window is shifted in any direction. This happens because the pixel RGB (or Intensity) values in the window are largely changed as it is shifted. This behavior of corners is greatly helpful for good localization, and therefore corners in the image are the local features that our detector is looking for.</p><p>Now, let’s take a look at how detectors work to find local features (specifically, corners).</p><h3>3. Harris Detector</h3><h4><strong>3.1 Second-moment matrix</strong></h4><p>We know that corners are regions in a given image with a large variation in intensity between pixels in all directions (i.e. large gradient magnitude). The Harris detector starts with this characteristic of corners. It finds pixel-intensity displacement of <em>(u, v)</em> such that the function <em>E</em> gets maximized for pixels in the window, as is expressed below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5OuephjgT7ANL6ybnzCjEA.png" /><figcaption><strong>Equation 1. derivation of the second moment matrix M, from [11]</strong></figcaption></figure><p>By applying the Taylor Expansion, we can represent <em>E(u, v) </em>in a form of matrix multiplication like the second line of the above equations. What is important here is the matrix <strong><em>M</em></strong> which is called the second-moment matrix, where <em>I𝑥</em> and <em>I𝑦 </em>are x and y-derivative, respectively.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oWNk8KFKQWk7OzFg4sqe4g.png" /><figcaption>chosen window function w(x, y) is the uniform window</figcaption></figure><p><strong>3.1.1 Then why the second-moment matrix is important?</strong></p><p>It’s because we can get a clue about whether a corner lies inside of the window or not, by looking at the matrix.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dy9oFKdZixyi1iBBC-kz2w.png" /><figcaption><strong>Figure 7. second-moment matrix of a window with axis-aligned corner, from [1, 2, 8]</strong></figcaption></figure><p>For example, let’s say our image window is like the one in <em>Fig 7, </em>which contains an axis-aligned corner. Then M is guaranteed to be a diagonal matrix, where non-diagonal entries (<em>I𝑥 × I𝑦) </em>are zero.</p><p>If why <em>I𝑥 × I𝑦 = 0 </em>is not clear, take a look at edge regions, which are marked with arrows in Fig 7.</p><ul><li>In vertical edge, <em>I𝑦 = 0 </em>as there is no chance in pixel intensity for pixels on the edge.</li><li>Similarly, in the horizontal edge, <em>Ix = 0.</em></li><li>In the flat regions, both<em> Ix </em>and<em> I𝑦 </em>are zero as pixel intensities do not change in both <em>x</em> and <em>y</em> directions.</li></ul><p>As described, the second-moment matrix is giving us a strong clue about the existence of a corner in a window. However, corners being axis-aligned is a too naive assumption in practice. We need to ensure that the second-moment matrix <strong><em>M</em></strong><em> </em>works in more general cases,<strong> i.e</strong>. it should be able to detect non-axis-aligned corners as well. Fortunately, the matrix <strong><em>M</em></strong> does detect!</p><p>The following figure shows the constructed <strong><em>M</em></strong> in general cases when a corner is not axis-aligned. By the definition of <strong><em>M</em></strong>, it is symmetric and therefore, it can be orthogonally diagonalizable (recall the characteristic of symmetric matrix regarding diagonalization).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rFyNoC5tHgWPzHcD20yXHQ.png" /><figcaption><strong>Figure 7. second-moment matrix of a window with non-axis-aligned corner, from [1, 2, 8]</strong></figcaption></figure><p><strong><em>M</em></strong> becomes a product of two rotation(orthogonal) matrices and a diagonal matrix whose entries are the eigenvalues. As one might notice, this diagonal matrix is what we need, again, in order to determine the existence of a corner.</p><blockquote>For further detail regarding how the ellipse in Fig 7 is constructed, please refer to <a href="https://guangchun.wordpress.com/2013/02/16/harris-detector/">[12]</a></blockquote><h4>3.2 Interpreting the second-moment matrix</h4><p>So far, we have constructed the matrix <strong><em>M</em></strong> which is the key component for corner detection. Now, the following content addresses how exactly the detector determines the existence of corner making use of the second-moment matrix <strong><em>M</em></strong>.</p><p>The bird’s eye view for interpreting M according to the eigenvalues are as below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9KWNneKBbwVO6gK_mXyTHw.png" /><figcaption><strong>Figure 8. Classification of image points, from [1, 2]</strong></figcaption></figure><p>For each image point (pixel) in the window, we compute the second-moment matrix <strong><em>M</em></strong> to obtain eigenvalues, and based on their values, the detector classifies the type of region that pixel belongs. The verbalized decision process for region classification is as follows.</p><ul><li>If one eigenvalue is significantly higher =&gt; derivative with respect to one direction is much stronger than the other =&gt; pixel lies on an edge</li><li>If both eigenvalues are small =&gt; pixel intensities do not change in any direction =&gt; pixel lies on a flat region</li><li>If both eigenvalues are large =&gt; pixel intensities largely chance in both <em>x</em> and <em>y</em> direction =&gt; pixel lies on a corner</li></ul><p>In order to automate the above process in a mathematical manner, the corner response function <strong><em>R</em></strong> is defined as is shown in <em>Fig 9</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*C7BUSlcQBHEoDe4A8mVooQ.png" /><figcaption><strong>Figure 9. Illustration of the usage of the corner response function, from [1, 2]</strong></figcaption></figure><p><strong>3.3 Choice of window function <em>w(x, y)</em></strong></p><p>Before summing up the Harris detector, one thing left is the candidates of window function <strong><em>w </em></strong>when the second-moment matrix <strong><em>M</em></strong> is computed. In the above figures, the uniform window is chosen as the window function. But it has one severe problem that the matrix <strong><em>M</em></strong> with the uniform window is not rotation invariant.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4KiOxoziO6L4y7uMgZdyEA.png" /><figcaption><strong>Figure 10. Gaussian smoothing vs uniform window as a window function, adapted from [1]</strong></figcaption></figure><p>An alternative window function to guarantee the rotation invariance is performing convolution with a Gaussian filter for each derivative map: <em>I𝑥², I𝑥 × I𝑦, I𝑦².</em></p><h4><strong>3.4 Steps of Harris Detector</strong></h4><p>We gain all the necessary knowledge about how the Harris detector finds local features (corners). All details above can be summarized in 5 steps (including non-maximum suppression: NMS after the 4th step).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QNYKtp-cVLcYDreuIUrW3w.png" /><figcaption>adapted from <a href="https://scholar.google.com/citations?user=s1IAWfgAAAAJ&amp;hl=en">Krystian Mikolajczyk</a></figcaption></figure><h4><strong>3.5 Experiment with Harris Detector</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wGwgnCnvP0peJLg9hUibaA.png" /><figcaption><strong>Figure 11. Left panel (Corner response map) vs right (given image with the detected corner as red blob)</strong></figcaption></figure><h3>4. Hessian Detector</h3><p>While the basic ideas of detecting corners remain the same as the Harris detector, the Hessian detector makes use of the Hessian matrix and determinant, instead of second-moment matrix <strong><em>M</em></strong> and corner response function <strong><em>R</em></strong>, respectively.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iitjk51xhdBwiAXB1s9CBw.png" /><figcaption><strong>Figure 12. Harris vs Hessian detector</strong></figcaption></figure><p><strong>Note that the entries in the Hessian matrix are the second derivatives.</strong></p><h3>5. Limitation</h3><p>Harris and Hessian detectors are rotation invariant. However, they are not scale-invariant, which is a crucial drawback in terms of feature detection. The reason why scale invariance is important is intuitively visualized in the following figure slide from <a href="http://vision.cs.utexas.edu/376-spring2018/">[2]</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nkJt5BX6WJEDbVAl-fOE0A.png" /></figure><p>Once a corner gets magnified and becomes bigger than the size of the window by zooming, the Harris and Hessian can no longer detect the corner. It is because what the detectors perceive through the window is not a corner anymore but an edge due to the scale change.</p><p>In order to overcome this limitation, a number of researches have been performed to create scale-invariant feature detectors, which will mainly be addressed in the next article.</p><h3>6. Reference</h3><p>[1] <a href="https://www.vision.rwth-aachen.de/courses/">RWTH Aachen, computer vision group</a></p><p>[2] <a href="http://vision.cs.utexas.edu/376-spring2018/">CS 376: Computer Vision of Prof. <strong>Kristen Grauman</strong></a></p><p>[3] <a href="https://homes.cs.washington.edu/~seitz/"><strong>S. Seitz</strong></a><br>[4] <a href="https://www.amazon.de/Computer-Vision-Approach-David-Forsyth/dp/013608592X"><strong>Forsyth &amp; Ponce</strong></a></p><p>[5] Prof. <a href="https://slazebni.cs.illinois.edu/"><strong>Svetlana Lazebnik</strong></a></p><p>[6] <a href="https://scholar.google.com/citations?user=5hJNWakAAAAJ&amp;hl=en">Prof <strong>M. Irani</strong></a> and <strong>R.</strong> <strong>Basri</strong></p><p>[7]<a href="https://scholar.google.com/citations?user=rDfyQnIAAAAJ&amp;hl=en"> Prof. <strong>Li fei-fei</strong></a></p><p>[8] <a href="https://scholar.google.com/citations?user=jkm1ipUAAAAJ&amp;hl=en">Denis Simakov</a></p><p>[9] <a href="https://scholar.google.com/citations?user=d97bGd8AAAAJ&amp;hl=ko">Alexej Efros</a></p><p>[10] <a href="https://www.cs.utexas.edu/~grauman/courses/fall2009/papers/local_features_synthesis_draft.pdf">Hessian-Laplace</a></p><p>[11] <a href="https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_features_harris/py_features_harris.html">openCV</a></p><p>[12] <a href="https://guangchun.wordpress.com/2013/02/16/harris-detector/">Harris ellipse derivation</a></p><p><strong>Any corrections, suggestions, and comments are welcome</strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7d524888abfd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/jun94-devpblog/cv-10-local-feature-descriptors-harris-and-hessian-corner-detector-7d524888abfd">[CV] 10. Local Feature Descriptors: Harris and Hessian Corner Detector</a> was originally published in <a href="https://medium.com/jun94-devpblog">Learning</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>