IMAGE DATA CODING METHODS AND SYSTEMSTECHNICAL FIELDThe present disclosure generally relates to image data processing, and more particularly, to methods and systems for encoding and decoding image data by subdividing and transforming synthetic image content.
BACKGROUNDLimited communication bandwidth poses challenges to transmitting images or videos (hereinafter collectively referred to as “image data” ) at desired quality. Although various coding techniques have been developed to compress the image data before it is transmitted, the increasing demand for massive amounts of image data has put a constant pressure on image/video systems, particularly mobile devices that frequently need to work in networks with limited bandwidth.
Moreover, with the rise of machine learning technologies and machine vision applications, the amount of video and images consumed by machines has rapidly grown. Typical use cases include intelligent transportation, smart city technology, intelligent content management, etc., which incorporate machine vision tasks such as object detection, instance segmentation, and object tracking. Machine vision applications extract and analyze features from image data. As feature information differs substantially from conventional image or video data, coding technologies and solutions for machine usage could differ from conventional human-viewing-oriented applications to achieve optimized performance. Therefore, there is a need to develop coding methods and systems suitable for machine usage.
SUMMARYEmbodiments of the present disclosure include an image data encoding method. The method includes: detecting a first object in an input image; determining a predetermined object image corresponding to the first object; partitioning the predetermined object image into one or more areas, wherein the partitioning comprises determining addresses of the one or more areas in the predetermined object image; determining transformation information associated with at least one of the one or more areas; modifying the input image by simplifying content of the first object; and encoding the modified image, the transformation information, and the address of the at least one of the one or more areas.
In some embodiments, a device for encoding image data is provided. The device includes a memory storing instructions; and one or more processors configured to execute the instructions to cause the device to perform operations including: detecting a first object in an input image; determining a predetermined object image corresponding to the first object; partitioning the predetermined object image into one or more areas, wherein the partitioning comprises determining addresses of the one or more areas in the predetermined object image; determining transformation information associated with at least one of the one or more areas; modifying the input image by simplifying content of the first object; and encoding the modified image, the transformation information, and the address of the at least one of the one or more areas.
In some embodiments, a decoding method is provided. The method includes: decoding a bitstream associated with an input image; reconstructing the input image based on the decoded bitstream; determining a predetermined object image based on the decoded bitstream; partitioning the predetermined object image into one or more areas, wherein the partitioning comprises determining addresses of the one or more areas in the predetermined object image; determining at least one of the one or more areas based on the addresses; modifying the predetermined object image by transforming the at least one of the one or more areas; and inserting the modified object image into the reconstructed image.
In some embodiments, a device for decoding image data is provided. The device includes a memory storing instructions; and one or more processors configured to execute the instructions to cause the device to perform operations including: decoding a bitstream associated with an input image; reconstructing the input image based on the decoded bitstream; determining a predetermined object image based on the decoded bitstream; partitioning the predetermined object image into one or more areas, wherein the partitioning comprises determining addresses of the one or more areas in the predetermined object image; determining at least one of the one or more areas based on the addresses; modifying the predetermined object image by transforming the at least one of the one or more areas; and inserting the modified object image into the reconstructed image.
Aspects of the disclosed embodiments include non-transitory, tangible computer-readable media that store software instructions that, when executed by one or more processors, are configured for and capable of performing and executing one or more of the methods, operations, and the like consistent with the disclosed embodiments. Also, aspects of the disclosed embodiments may be performed by one or more processors that are configured as special-purpose processor (s) based on software instructions that are programmed with logic and instructions that perform, when executed, one or more operations consistent with the disclosed embodiments.
Additional features and advantages of the disclosed embodiments will be set forth in part in the following description, and in part will be apparent from the description, or may be learned by practice of the embodiments. The features and advantages of the disclosed embodiments may be realized and attained by the elements and combinations set forth in the claims.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the disclosed embodiments, as claimed.
BRIEF DESCRIPTION OF THE DRAWINGSFIG. 1 is a block diagram illustrating an exemplary architecture for a video-coding-for-machines (VCM) system, consistent with embodiments of the present disclosure.
FIG. 2 is a flowchart of an exemplary image data encoding method, consistent with embodiments of the present disclosure.
FIG. 3 is a schematic diagram illustrating an image inpainting process, consistent with embodiments of the present disclosure.
FIG. 4 is a flowchart of an exemplary image data decoding method, consistent with embodiments of the present disclosure.
FIG. 5 is a schematic diagram illustrating a process for inserting synthetic content into an image, consistent with embodiments of the present disclosure.
FIG. 6 is a flowchart of an exemplary method for partitioning image features extracted from an image, consistent with embodiments of the present disclosure.
FIG. 7 is a schematic diagram illustrating an exemplary scale invariant feature transform (SIFT) keypoint, consistent with embodiments of the present disclosure.
FIG. 8 is a schematic diagram illustrating a predetermined object image selected from a dictionary, consistent with embodiments of the present disclosure.
FIG. 9 is a schematic diagram illustrating a keypoint map including keypoints extracted from the predetermined object image in FIG. 8, consistent with embodiments of the present disclosure.
FIG. 10 is a schematic diagram illustrating a convex hull of the keypoint map in FIG. 9, consistent with embodiments of the present disclosure.
FIG. 11 is a schematic diagram illustrating an exemplary Jarvis march algorithm, consistent with embodiments of the present disclosure.
FIG. 12 is a schematic diagram illustrating positions of initial medoids used for a medoid clustering algorithm, consistent with embodiments of the present disclosure.
FIG. 13 is a schematic diagram illustrating positions of medoids generated by a medoid clustering algorithm, consistent with embodiments of the present disclosure.
FIG. 14 is a Voronoi diagram representing a two-dimensional space with keypoints grouped into clusters, consistent with embodiments of the present disclosure.
FIG. 15 is a Voronoi diagram restricted to the area of an object image, consistent with embodiments of the present disclosure.
FIG. 16 illustrates an exemplary process for transforming two subdivided areas in a predetermined object image, consistent with embodiments of the present disclosure.
FIG. 17 illustrates an exemplary process for transforming two subdivided areas in a predetermined object image, consistent with embodiments of the present disclosure.
FIG. 18 illustrates an exemplary process for transforming two subdivided areas in a predetermined object image, consistent with embodiments of the present disclosure.
FIG. 19 is a block diagram of an exemplary apparatus for encoding or decoding image data, consistent with embodiments of the present disclosure.
DESCRIPTION OF THE EMBODIMENTS
Reference will now be made in detail to exemplary embodiments, examples of which are illustrated in the accompanying drawings. The following description refers to the accompanying drawings in which the same numbers in different drawings represent the same or similar elements unless otherwise represented. The implementations set forth in the following description of exemplary embodiments do not represent all implementations consistent with the invention. Instead, they are merely examples of apparatuses and methods consistent with aspects related to the invention as recited in the appended claims.
The present disclosure provides an encoding and decoding architecture and method for compressing image data, including image data for machine vision applications. The disclosed architecture and method include a Video Coding for Machines (VCM) technique that aims at compressing features for machine-performed tasks such as video object detection, event analysis, object tracking and others. The input (original) and the output (decoded) of the disclosed VCM architecture is a still image or video (i.e., a sequence of images) . The architecture includes an encoder, communication/storage system of any type, and a decoder. The architecture is designed to represent the input image or video with possibly low bitrate but assuring possibly high efficiency of machine vision tasks executed on the output (decoded) image or video. The architecture and method are suitable for compressing image data used by a variety of machine vision tasks. For example, the architecture and method can be used to improve the average precision of detection or segmentation executed on the output image or video. As another example, they can be used to improve the tracking performance in the output video.
FIG. 1 is a block diagram illustrating an exemplary architecture for a VCM system 10, consistent with embodiments of the present disclosure. As shown in FIG. 1, VCM system 10 includes an encoder 110 and a decoder 120. Encoder 110 further includes a pre-processing module 114 and an encoding module 116. Decoder 120 further includes a decoding module 122 and a post-processing module 124.
Pre-processing module 114 receives data comprising an input image 112, which may be a still image, part of an image stream, part of a video, etc. Pre-processing module 114 is configured to modify input image 112 by simplifying its content, to reduce the bitrate. For example, the simplification may include removing certain objects from input image 112. The output of pre-processing module 114 includes the modified image data and metadata describing the modification performed on the original input image.
The output of pre-processing module 114 is provided to encoding module 116, which is configured to encode (i.e., compress) the modified image data and the metadata. Encoding module 116 may operate according to any image/video coding standard, such as Advanced Video Coding (AVC) , High Efficiency Video Coding (HEVC) , Versatile Video Coding (VVC) , AOMedia Video 1 (AV1) , Joint Photographic Experts Group (JPEG) , Moving Picture Experts Group (MPEG) , etc. Encoding module 116 outputs an encoded bitstream 130 including the encoded image data and metadata.
Encoded bitstream 130 is provided to decoding module 122, which decodes the bitstream and generates a reconstructed image. Decoding module 122 may perform the decoding according to any existing standard, such as AVC, HEVC, VVC, AV1, JPEG, MPEG, etc.
Post-processing module 124 processes, based on the metadata, the reconstructed image to restore the original input image. For example, post-processing module 124 may generate synthetic content representative of the objects removed by pre-processing module 114, and insert the synthetic content into the reconstructed image. Post-processing module 124 outputs the resulting image as output image 126, which can be utilized by downstream vision applications, e.g., object detection, instance segmentation, and object tracking. With the synthetic content, output image 126 closely mimics input image 112, and thus can ensure the average precision of detection or segmentation executed on output image 126.
Moreover, as described above, the synthetic content does not need to be transmitted from encoder 110 to decoder 120, thereby reducing the bitrate. Consistent with the disclosed embodiments, encoder 110 and decoder 120 each can store a same “dictionary, ” i.e., database, of predetermined object images. The synthetic content can be drawn from the dictionary. Specifically, at the encoder side, pre-processing module 114 selects, from the dictionary, a predetermined object image matching the content to be simplified (e.g., an object to be removed) . Pre-processing module 114 outputs the identification information of the selected predetermined object image, as part of the metadata transmitted to decoder 120. Then, at the decoder side, post-processing module 124 uses the metadata to select the same predetermined object image from the dictionary, and inserts it into the reconstructed image to generate a synthesized image. This way, VCM system 10 can be used to represent the input images or videos with low bitrate while assuring high efficiency and precision of machine vision tasks executed on the output (decoded) images or videos. VCM system 10 is suitable for use with a wide variety of machine vision applications. For example, VCM system 10 can be used to maximize the average precision of object detection or segmentation executed on the output images or videos. As another example, VCM system 10 can be used to maximize the tracking performance based on the output images or videos. The machine vision applications of VCM system 10 are not limited to the aforementioned examples.
Consistent with the disclosed embodiments, the predetermined object image (i.e., synthetic content) drawn from the dictionary may not match the simplified content (i.e., an object removed by the encoder) at a desirable level. For example, the size, orientation, color, and/or brightness of the predetermined object image may be different from the simplified content. Thus, the decoder needs to perform a certain transformation on the predetermined object image to make it better match the simplified content. Therefore, transformations are performed on individual samples belonging to the predetermined object image. However, addressing these individual samples would require a large amount of additional information to be encoded and transmitted in the bitstream. To solve this problem, the disclosed embodiments provide a method to address the individual samples in the predetermined object image. The method can be used on both the encoder side and the decoder side.
FIG. 2 is a flowchart of an exemplary encoding method 200, consistent with embodiments of the present disclosure. Method 200 is performed by an image data encoder, e.g., encoder 110 in FIG. 1. As shown in FIG. 2, method 200 includes the following steps 210-260.
In step 210, the encoder detects a first object in an input image. In some embodiments, the first object may be detected through region-of-interest (ROI) analysis. An ROI is a region in the input image that contains one or more objects. The encoder analyzes the input image and determines one or more ROIs. In some embodiments, the detection of object (s) in an input image includes three stages: image segmentation (i.e., object isolation or recognition) , feature extraction, and object classification.
At the image segmentation stage, the encoder executes an image segmentation algorithm to partition the input image into multiple segments, e.g., sets of pixels each of which represent a portion of the input image. The image segmentation algorithm assigns a label (e.g., category) to each set of pixels, such that pixels with the same label share certain common characteristics. The encoder then groups the pixels according to their labels and designates each group as a distinct object.
After the input image is segmented, i.e., after at least one object is recognized, at the feature extraction stage, the encoder extracts, from the input image, features which are characteristic of the object. The features may be based on a size of the object or on its shape, such as an area of the object, a length and a width of the object, a distance around a perimeter of the object, rectangularity of an object shape, circularity of the object shape, etc. The features associated with each object can be combined to form a feature vector.
At the object classification stage, the encoder classifies each recognized object on the basis of the feature vector associated with the respective object. Feature values can be viewed as coordinates of a point in an N-dimensional space (one feature value implies a one-dimensional space, two features imply a two-dimensional space, and so on) , and the classification is a process for determining a sub-space of a feature space to which the feature vector belongs. Since each sub-space corresponds to a distinct object, the classification accomplishes the task of object identification. For example, the encoder may classify a recognized object into one of multiple predetermined classes, such as human, face, animal, automobile, or vegetation. In some embodiments, the encoder may perform the classification based on a model. The model may be trained using pre-labeled training data sets that are associated with known objects. In some embodiments, the encoder may perform the classification using a machine learning technology, such as a convolutional neural network (CNN) , a deep neural network (DNN) , etc.
The result of ROI determination and classification can be used by the encoder to simplify the content of the input image. In particular, the encoder can remove certain less important objects from the input image, and replace them with image elements with simple content, so that no holes are left in the image. For example, in step 210, the encoder determines a first object to be removed from the input image. The detailed process for removing the less important, removed objects is described below in connection with step 250.
With continued reference to FIG. 2, in step 220, the encoder determines a predetermined object image corresponding to the first object. Specifically, the encoder stores a dictionary of predetermined object images. The dictionary contains multiple classes of object images, e.g., dogs, horses, people, apples, cars, etc. And each class further includes multiple object images, e.g., woman standing, woman walking, woman sitting, woman in front, woman on the side, etc. The encoder selects, from the dictionary, a predetermined object image that matches the first object. The selection may be based on a comparison of the first object to the predetermined object images in the dictionary in terms of their classes, shapes, and contents.
In step 230, the encoder partitions the predetermined object image into one or more areas, and determines addresses of the one or more areas in the predetermined object image. For example, the encoder may detect a plurality of image features in the predetermined object image, partition the plurality of image features into one or more clusters, and partition the predetermined object image into the one or more areas based on the one or more clusters. In each cluster, there is one image feature serving as a medoid feature of the respective cluster, and the rest of the images feature in the cluster are non-medoid features. The medoid of a cluster is defined as one of the cluster’s image features whose sum of distances to all the other image features in the cluster is minimal. The partitioning technique will be described below in more detail.
Moreover, the encoder may index the one or more clusters and use the indexes of the clusters to address the one or more areas in the predetermined object image. Specifically, the one or more areas are associated with the one or more clusters respectively; thus, the addresses of the one or more areas can be represented by the indexes of the one or more clusters respectively.
In step 240, the encoder determines transformation information associated with at least one of the one or more areas. Specifically, the encoder may determine that at least one of the one or more areas needs to be transformed to make the predetermined object image better match the first object. The transformation may include: shifting (spatially translating) the at least one of the one or more areas; rotating the at least one of the one or more areas; rescaling (i.e., resizing) the at least one of the one or more areas; adjusting a brightness of the at least one of the one or more areas; adjusting a color of the at least one of the one or more areas, and so on.
Moreover, the encoder may determine reference coordinates for applying the transformation to the at least one of the one or more areas. The reference coordinates are coordinates associated with a medoid feature in the at least one of the one or more areas, and the transformation is performed relative to the reference coordinates.
Additionally, the encoder generates transformation information descriptive of the transformation, so that the transformation information can be provided to a decoder to facilitate decoder-side transformation. The transformation information may include, for example: identification information of the predetermined object image (e.g., object class, index of the predetermined object image in the dictionary) ; an index indicating an address of the at least one of the one or more areas in the predetermined object image; a transformation parameter associated with a transformation to be applied to the at least one of the one or more areas (e.g., a target size) ; and a target location in the image for inserting the predetermined object image.
In step 250, the encoder modifies the input image by simplifying content of the first object. In some embodiments, to simplify the content, the encoder may remove certain less important objects (e.g., the first object) from the input image, and replace them with image elements with simple content, so that no holes are left in the image. The less important, removed objects may be small objects or objects repeatedly showing in the image. As described below in connection with the decoder, the removed objects can be synthesized by the decoder and added back to the decoded image. In exemplary embodiments, the image area originally occupied by a removed object may be inpainted by simple content that is represented by a small number of bits. In the context of image processing, “inpainting” refers to a process of initially removing certain content from an image (e.g., by an encoder) , and restoring the content at a later time (e.g., by a decoder) .
FIG. 3 is a schematic diagram illustrating an image inpainting process 300, according to some exemplary embodiment consistent with the present disclosure. As shown in FIG. 3, the encoder, e.g. encoder 110 in FIG. 1, determines objects 312a, 314a, 316a, and 318a from an original image 310a. The encoder removes objects 312a, 314a, 316a, and 318a, and inpaints the affected image areas using the content and color surrounding the removed objects, to generate an inpainted image 310b.
Referring back to FIG. 2, in step 260, the encoder encodes the modified image, the transformation information, and the address (e.g., the index) of the at least one of the one or more areas. The encoder performs compression (i.e., encoding) according to any image data coding standard, such as AVC, HEVC, VVC, AV1, JPEG, MPEG, etc., and generates an encoded bitstream. The encoder also encodes the transformation information into the bitstream, to facilitate decoding. In some embodiments, the transformation information can be sent in extension fields allowed by the chosen standard.
Correspondingly, FIG. 4 is a flowchart of an exemplary decoding method 400, consistent with embodiments of the present disclosure. Method 400 is performed by an image data decoder, e.g., decoder 120 in FIG. 1. As shown in FIG. 4, method 400 includes the following steps 410-470.
In step 410, the decoder decodes a bitstream associated with an image. The bitstream includes encoded image data and transformation information. For example, the transformation information may include: identification information of a predetermined object image (e.g., object class, index of the predetermined object image in the dictionary) ; an index indicating an address of the at least one of the one or more areas in the predetermined object image; a transformation parameter associated with a transformation to be applied to the at least one of the one or more areas (e.g., a target size) ; and the target location in the image (included in the transformation information generated in step 240 by the encoder) for inserting the predetermined object image. The decoder decodes the bitstream based on any existing image or video coding standard, such as AVC, HEVC, VVC, AV1, JPEG, MPEG, etc.
In step 420, the decoder reconstructs the image based on the decoded bitstream.
In step 430, the decoder determines a predetermined object image based on the decoded bitstream. The decoder stores the same dictionary of predetermined object images as the encoder. Based on the identification information of the predetermined object image, the decoder selects the predetermined object image from the dictionary.
In step 440, the decoder partitions the predetermined object image into one or more areas and determines addresses of the one or more areas in the predetermined object image. The same partitioning process used by the encoder (step 230 in method 200) is used by the decoder. Namely, the partitioning includes: detecting a plurality of image features in the predetermined object image; partitioning the plurality of image features into one or more clusters; and partitioning the predetermined object image into the one or more areas based on the one or more clusters. Moreover, the decoder may index the one or more clusters and use the indexes of the clusters to address the one or more areas in the predetermined object image. Specifically, the one or more areas are associated with the one or more clusters respectively; thus, the addresses of the one or more areas can be represented by the indexes of the one or more clusters respectively.
In step 450, the decoder determines at least one of the one or more areas based on the addresses. Specifically, the address (e.g., index) of the at least one of the one or more areas may be signaled in the in the bitstream, such that the decoder may use the signaled address (e.g., index) to locate the at least one of the one or more areas in the predetermined object image.
In step 460, the decoder modifies the predetermined object image by transforming the at least one of the one or more areas. The transformation includes, for example: shifting the at least one of the one or more areas; rotating the at least one of the one or more areas; rescaling the at least one of the one or more areas; adjusting a brightness of the at least one of the one or more areas; adjusting a color of the at least one of the one or more areas, and so on. To perform the transformation, the decoder may determine coordinates associated with a medoid feature in the at least one of the one or more areas, and transform the at least one of the one or more areas relative to the coordinates associated with the medoid feature. The transformation is performed based on the transformation parameter signaled in the bitstream.
In step 470, the decoder inserts the modified object image into the reconstructed image. The decoder may insert the modified object image into the target location in the reconstructed image.
FIG. 5 is a schematic diagram illustrating an exemplary process 500 for inserting synthetic content into an image, consistent with embodiments of the present disclosure. As shown in FIG. 5, at the decoder side, ROI synthesis is performed on a reconstructed image 530, in which image elements 532, 534, 536, and 538 are replaced by ROIs 552, 554, 556, and 558, respectively. ROIs 552, 554, 556, and 558 include predetermine object images that are in the same or similar classes as objects 512, 514, 516, and 518.
The above-described encoding method 200 (FIG. 2) and decoding method 400 (FIG. 4) use the same way to partition the predetermined object image and to address the subdivided areas in the predetermined object image. At the decoder side, various transformations can be performed on the predetermined object image, e.g., rotating by an angle, performing a spatial translation, rescaling, correcting brightness or color, etc. Such exemplary transformations can better match the predetermined object image to the nature of the simplified content on the decoder side and at the same time better approximate the source image before simplification.
The transformation information is signaled explicitly in the bitstream transmitted between the encoder and the decoder. Specifically, if the encoder decides that certain subdivided areas in the predetermined object are to be transformed (e.g., shifted, rotated, up-scaled or down-scaled, correcting brightness or color, etc. ) , the encoder sends, to the decoder, the indexes of the areas to which the selected transformations are to be performed, as well as the transformation information.
Various techniques can be used in the above-described encoding method 200 (step 230, FIG. 2) and decoding method 400 (step 440, FIG. 4) to partition the predetermined object image. For example, FIG. 6 is a flowchart of an exemplary partitioning method 600, consistent with embodiments of the present disclosure. The image features used by method 600 are scale invariant feature transform (SIFT) keypoints known in the art. In some embodiments, the SIFT keypoints may be keypoints which, with minor modifications not relevant to this disclosure, are used in the MPEG-7 CDVS standard and the MPEG-7 CDVA standard. The MPEG-7 CDVS standard is developed to use local descriptors to describe features in a static image, while the MPEG-7 CDVA standard is developed to use local descriptors to describe features in a video sequence (i.e., a sequence of consecutive frames) . The SIFT technique is described by D.G. Lowe in “Distinctive Image Features from Scale-Invariant Keypoints, ” International Journal of Computer Vision, Vol. 60, No. 2, pp. 91-110, 2004. Referring to FIG. 6, method 600 includes the following steps 610-650.
In step 610, a codec (i.e., an encoder or a decoder) extracts keypoints from the predetermined object image. FIG. 7 is a schematic diagram illustrating an exemplary keypoint 710 in a scale space of an image 700, consistent with embodiments of the present disclosure. The scale space is described by a function that is produced from the convolution of a Gaussian kernel (at different scales) and image 700. As shown in FIG. 7, keypoint 710 may be described by various parameters, including, for example: keypoint position (x, y) in an image scale space in which keypoint 710 is detected, scale σ (a radius of the keypoint in the scale space) , and orientation θ (an angle of the keypoint in the image scale space, expressed in radians) . The scale or radius σ describes the extent of the area keypoint 710 occupying the scale space, and depends on the keypoint’s position (x, y) in the image scale space. In some embodiments, keypoint 710 is also accompanied by a descriptor (not shown) of the area occupied by keypoint 710. The descriptor is a 3-dimensional spatial histogram of the image gradients in characterizing the appearance of a keypoint. The gradient at each pixel is regarded as a sample of a three-dimensional elementary feature vector, formed by the pixel location and the gradient orientation. Samples are weighted by the gradient norm and accumulated in a 3-dimensional histogram, which forms the SIFT descriptor of the region. An additional Gaussian weighting function may be applied to the SIFT descriptor to give less importance to gradients farther away from the keypoint.
By applying the SIFT technique, the codec can extract a plurality of keypoints from the predetermined object image. The keypoints describe the image points that are distinctive and invariant to changes such as viewpoint change or illumination change. The keypoint extraction yields a set of data vectors that describe successive keypoints and their accompanying descriptors. For example, FIG. 8 shows an exemplary predetermined object image 80, and FIG. 9 shows a corresponding keypoint map 90 including keypoints 92 extracted from predetermined object image 80. Each keypoint 92 is mathematically represented by a vector.
Referring back to FIG. 6, in step 620, the codec determines a convex hull of the keypoints extracted from the predetermined object image. A convex hull of a set of keypoints is the smallest convex polygon that contains all the keypoints in the set. FIG. 10 is a schematic diagram illustrating a convex hull 94 of the keypoint map 90 in FIG. 9, consistent with embodiments of the present disclosure. In FIG. 10, convex hull 94 is shown as a solid-line polygon encompassing all the keypoints.
A convex hull determination algorithm, for example, a Jarvis march algorithm, can be used to determine the convex hull. FIG. 11 is a schematic diagram illustrating an exemplary method for implementing the Jarvis march algorithm. As shown in the FIG. 11 example, the Jarvis march algorithm starts with a left-most keypoint P0 and looks for convex-hull keypoints in a counter-clockwise direction. Specifically, the Jarvis march algorithm starts from the left-most keypoint P0 and finds the next convex-hull keypoint P1 which has the largest angle (Angle-0 in FIG. 11) from P0. The Jarvis march algorithm then starts from keypoint P1 and finds the next convex-hull keypoint P2 which has the largest angle (Angle-1 in FIG. 11) from P1. using the origin to calculate an angle between every other point in the simulation. The Jarvis march algorithm repeats the above process until it returns to the left-most keypoint P0. The set of keypoints chosen in this way constitute the convex hull.
Referring back to FIG. 6, in step 630, the codec identifies the keypoints located on the convex hull, which can be used as initial medoids for a clustering process. For example, FIG. 12 illustrates that there are M keypoints 96 (cross marks) located on convex hull 94 determined in FIG. 10.
Referring back to FIG. 6, in step 640, the codec partitions the keypoints of the predetermined object image into one or more clusters based on the keypoints located on the convex hull. In some embodiments, a medoid clustering algorithm, for example, a Partitioning Around Medoids (PAM) algorithm, is used to partition the keypoints and determine the medoid of each cluster. The PAM algorithm searches for a set of representative data points in an input data set and then assigns the remaining data points to the closest medoid in order to create clusters. The representative data point of a cluster is also called the “medoid” of the cluster and is the mathematical center of the cluster. The remaining data points in the cluster are called “non-medoids. ” In some embodiments, the PAM algorithm may be implemented in three steps. In the first step, the PAM algorithm chooses, from the input data set, one or more data points as initial medoids. The one or more initial medoids correspond to one or more clusters, respectively. In the second step, the PAM algorithm associates each of the remaining data points with its closest initial medoid. In the third step, the PAM algorithm searches for the optimum medoid for each cluster, by minimizing a cost function that measures the sum of dissimilarities between the medoid and the other data points in the same cluster.
In some embodiments, the keypoints located on the convex hull are used as initial medoids of the medoid clustering algorithm. For example, FIG. 13 illustrates that the medoid clustering algorithm results in M clusters of keypoints, each of the resulting clusters having a medoid 98 (cross mark) . Thus, the keypoints located on the convex hull uniquely define the number of clusters to be partitioned into. In other words, the number of clusters generated by the medoid clustering algorithm is equal to the number of the keypoints located on the convex hull. This ensures that the encoder and decoder use the same method to determine initial medoids, hence results in the same clusters and medoids being generated on both the encoder and decoder sides.
Referring back to FIG. 6, step 640 outputs coordinates 645 of the determined medoids. Coordinates 645 are also called “indexes” of the respective medoids and clusters. The indexes are used to indicate the addresses of the subdivided areas associated with the respective medoids.
In step 650, the codec partitions the predetermined object image into one or more areas, based on the one or more clusters. FIG. 14 is a Voronoi diagram 140 showing that a rectangular bounding box associated with the predetermined object image is divided into areas 142 corresponding to the clusters. Voronoi diagram 140 is generated based on the medoids of the one or more clusters, such that each area in Voronoi diagram 140 is associated with a different medoid and the points in each area are closer to the respective medoid than to the other medoids. FIG. 15 shows that Voronoi diagram 140 can be restricted to the predetermined object image, to generate a restricted Voronoi diagram 150 including areas 152 associated with respective medoids 98. The disclosed embodiments are not limited to using the Voronoi diagram technique. Other techniques known in the art can also be used to explicitly divide the predetermined object image into one or more areas based on the one or more clusters.
As a result of partitioning method 600 (FIG. 6) , each point of the predetermined object image is unambiguously assigned to one of M areas. The addressing of these areas is unambiguous on the encoder and decoder sides and results from the indexing of the medoids, which is the result of assigning the keypoints of the convex hull as initiating medoids. In other words, the keypoints of the convex hull are unique. By using the keypoints of the convex hull as initiating medoids for performing the clustering, the encoder and decoder would arrive at the same set of clusters and the same set of cluster indexes. Accordingly, such cluster indexes can be unambiguously used by the encoder and decoder to address (i.e., locate) the M areas in the predetermined object image.
Since the addressing of areas disclosed herein does not impact any content in the visual object area, the technique is scalable. The input of the partitioning algorithm can include areas already partitioned, i.e., keypoint clusters, and the partitioned areas will be the areas resulting from step 640 of partitioning method 600. For example, method 600 can be executed in multiple iterations including, e.g., a first iteration and a second iteration. In the first iteration, method 600 partitions a plurality of keypoints into a first plurality of clusters. Then, in the second iteration, at least one of the first plurality of clusters can be further partitioned into smaller clusters. In the disclosed embodiments, method 600 can be performed in any number of iterations. Since an address map of the areas needs to be known at both the encoder and the decoder, the decision for scalable partitioning needs be communicated to the decoder, or established as an initial assumption. The effect of such scalable partitioning is that the area of a predetermined object image from the dictionary can be partitioned more flexibly. It is noted there is a cost to increase the list of addresses and thus the number of bits needed to indicate areas. assuming the necessary area transformation information is sent.
FIG. 16, FIG. 17 and FIG. 18 illustrate an exemplary process for transforming (e.g., extending in the x-direction) two areas in predetermined object image 80 of FIG. 8. As shown FIG. 16, the contour of the shape of predetermined object image 80 is shown as a solid line. The encoder determines two subdivided areas 162 and 164 need to be transformed. The addresses of these two areas in predetermined object image 80 are indicated by the indexes of their medoids (shown as cross marks) , respectively. The encoder sends the transformation information (including, e.g., address information of areas 162 and 164, type of transformation, transformation parameter, etc. ) to the decoder. The intended results of the transformations (i.e., extensions in the x-direction) are shown as dash lines in FIG. 16. FIG. 17 shows the effect of applying the transformations to areas 162 and 164. And FIG. 18 shows the end result of integrating the transformed areas 162 and 164 to predetermined object image 80.
In summary, the disclosed embodiments provide an efficient way of addressing a coherent fragment of a synthetic area by using the combined techniques of keypoint determination, medoidal grouping of keypoints, and partitioning of the object area from the dictionary relative to the grouped keypoints. In particular, the disclosed embodiments partition a predetermined object image selected from a dictionary into multiple smaller areas, including precise knowledge of the number and location of the areas on both the encoder and decoder sides, without the need to transfer information between the encoder and decoder.
The disclosed embodiments distinguish between the introduced transformations for parts of a visual object, thus achieving a significantly smaller difference between the object (s) to be removed from the image and the image content after inserting the object (s) from the dictionary. This enables better segmentation to be achieved, or better object detection to be achieved, on the decoder side in VCM applications.
Next, a hardware environment for implementing the disclosed encoder and decoder is described. FIG. 19 shows a block diagram of an exemplary apparatus 1900 for encoding or decoding image data, according to some embodiments of the present disclosure. As shown in FIG. 19, apparatus 1900 can include a processor 1902. When processor 1902 executes instructions consistent with the techniques described herein, apparatus 1900 can become a specialized machine for processing the image data. Processor 1902 can be any type of circuitry capable of manipulating or processing information. For example, processor 1902 can include any combination of any number of a central processing unit (or “CPU” ) , a graphics processing unit (or “GPU” ) , a neural processing unit ( “NPU” ) , a microcontroller unit ( “MCU” ) , an optical processor, a programmable logic controller, a microcontroller, a microprocessor, a digital signal processor, an intellectual property (IP) core, a Programmable Logic Array (PLA) , a Programmable Array Logic (PAL) , a Generic Array Logic (GAL) , a Complex Programmable Logic Device (CPLD) , a Field-Programmable Gate Array (FPGA) , a System On Chip (SoC) , an Application-Specific Integrated Circuit (ASIC) , or the like. In some embodiments, processor 1902 can also be a set of processors grouped as a single logical component. For example, as shown in FIG. 19, processor 1902 can include multiple processors, including processor 1902a, processor 1902b, ..., and processor 1902n.
Apparatus 1900 can also include a memory 1904 configured to store data (e.g., a set of instructions, computer codes, intermediate data, or the like) . For example, as shown in FIG. 19, the stored data can include program instructions (e.g., program instructions for implementing the processing of image data) and image data to be processed. Processor 1902 can access the program instructions and data for processing (e.g., via a bus 1910) , and execute the program instructions to perform an operation or manipulation on the data. Memory 1904 can include a high-speed random-access storage device or a non-volatile storage device. In some embodiments, memory 1904 can include any combination of any number of a random-access memory (RAM) , a read-only memory (ROM) , an optical disc, a magnetic disk, a hard drive, a solid-state drive, a flash drive, a security digital (SD) card, a memory stick, a compact flash (CF) card, or the like. Memory 1904 can also be a group of memories (not shown in FIG. 19) grouped as a single logical component.
Bus 1910 can be a communication device that transfers data between components inside apparatus 1900, such as an internal bus (e.g., a CPU-memory bus) , an external bus (e.g., a universal serial bus port, a peripheral component interconnect express port) , or the like.
For ease of explanation without causing ambiguity, processor 1902 and other data processing circuits (e.g., analog/digital converters, application-specific circuits, digital signal processors, interface circuits, not shown in FIG. 19) are collectively referred to as a “data processing circuit” in this disclosure. The data processing circuit can be implemented entirely as hardware, or as a combination of software, hardware, or firmware. In addition, the data processing circuit can be a single independent module or can be combined entirely or partially into any other component of apparatus 1900.
Apparatus 1900 can further include a network interface 1906 to provide wired or wireless communication with a network (e.g., the Internet, an intranet, a local area network, a mobile communications network, or the like) . In some embodiments, network interface 1906 can include any combination of any number of a network interface controller (NIC) , a radio frequency (RF) module, a transponder, a transceiver, a modem, a router, a gateway, a wired network adapter, a wireless network adapter, a Bluetooth adapter, an infrared adapter, a near-field communication ( “NFC” ) adapter, a cellular network chip, or the like.
In some embodiments, optionally, apparatus 1900 can further include a peripheral interface 1908 to provide a connection to one or more peripheral devices. As shown in FIG. 19, the peripheral device can include, but is not limited to, a cursor control device (e.g., a mouse, a touchpad, or a touchscreen) , a keyboard, a display (e.g., a cathode-ray tube display, a liquid crystal display, or a light-emitting diode display) , an image/video input device (e.g., a camera or an input interface coupled to an image/video archive) , or the like.
In some embodiments, a non-transitory computer-readable storage medium including instructions is also provided, e.g., included in memory 1904, and the instructions may be executed by a device (such as the disclosed encoder and decoder) , for performing the above-described methods. Common forms of non-transitory media include, for example, a floppy disk, a flexible disk, hard disk, solid state drive, magnetic tape, or any other magnetic data storage medium, a CD-ROM, any other optical data storage medium, any physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM or any other flash memory, NVRAM, a cache, a register, any other memory chip or cartridge, and networked versions of the same. The device may include one or more processors (CPUs) , an input/output interface, a network interface, and/or a memory.
It should be noted that, the relational terms herein such as “first” and “second” are used only to differentiate an entity or operation from another entity or operation, and do not require or imply any actual relationship or sequence between these entities or operations. Moreover, the words “comprising, ” “having, ” “containing, ” and “including, ” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items.
As used herein, unless specifically stated otherwise, the term “or” encompasses all possible combinations, except where infeasible. For example, if it is stated that a database may include A or B, then, unless specifically stated otherwise or infeasible, the database may include A, or B, or A and B. As a second example, if it is stated that a database may include A, B, or C, then, unless specifically stated otherwise or infeasible, the database may include A, or B, or C, or A and B, or A and C, or B and C, or A and B and C.
It will be appreciated that the present invention is not limited to the exact construction that has been described above and illustrated in the accompanying drawings, and that various modifications and changes can be made without departing from the scope thereof. It is intended that the scope of the invention should only be limited by the appended claims.